When function pkix_Build_VerifyCertificate comes to a self-signed root CA cert that is not trusted, it incorrectly determines that the chain has a loop. This apparently causes libPKIX to stop checking for other possible paths that might lead to other roots, and instead report that it cannot build a path. libPKIX has a function to determine if a cert is self-signed, but does not use it here. I think I can tackle this in Alexei's absence.

Sadly, pkix_IsCertSelfIssued() is wrong. It ignores key IDs.

So I went looking throughout libPKIX for a function that can test the SubjectKeyID extension in an issuer cert against the AuthorityKeyID extension in a subordinate cert, and found none. That's right, it appears there is NO code in libPKIX to properly test subject and authority key ID extensions against each other. I hope I'm wrong, but I really don't see it. Instead I found some silly code that compares two authority key IDs to each other as byte strings. Thankfully, that nonsense appears to be dead code, other than being tested in unit tests. We really should get rid of it.

The erroneous loop detection code is at http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/security/nss/lib/libpkix/pkix/top/pkix_build.c&rev=1.57&mark=897-921#889 The mere presence of a root in the chain does not constitute looping. To fix this, the code must CORRECTLY identify roots. That means that pkix_IsCertSelfIssued needs to be fixed before this bug can be fixed. Alexei, I'm giving this back to you. If you're bored ... :)

I'm not sure if you have found this problem by review of a test. Would be great to have a test if you have one. But I'm quite convinced we have the problem but it is not related to pkix_IsCertSelfIssued. I think the function is correct(self-signed certs set is a subset of self-issued certs) and is used in proper places(when chain is already built), although we need test cases(see below). Consider the chain: CAI -> CAII -> CAII(Self-Issued) -> EE The problem that I see is inefficiency when dealing with self-issued certs in cases when chain CAI,CAII,EE is constructed and discarded due to failure to validate EE cert signature. I case when CAII(SI)->EE is built first, the libpkix traverses through all certs in the chain to detect a loop. pkix_pl_Cert_Equals function is used for this operation. It calls CERT_CompareCerts(plain cert DERs comparison) to compare the pair therefor will distinguish two cert of the same subject names(CAII and CAII(SI)). Here is some tasks for Slavo: we don't have even one test that would check that libpkix correctly handles Self-Issued(SI) certificates. There are a few areas where we need some testing: * Name Constraints/name validation should not be applied to SI certs(except the final cert). * Should be ignored when calculating any path lengths(cert path, Basic Constraints, explicit policy, policy mapping). It should also be ignored when calculating number of certs to be processed before inhibiting anyPolicy. * Signature checks for crls that do or don't have authKeyId extensions.

Alexei, I agree that pkix_IsCertSelfIssued is not part of the problem. Sadly, it is also not part of the solution. I was lamenting that fact.

In comment 3, I wrote: > That means that pkix_IsCertSelfIssued needs to be fixed before this bug > can be fixed. That was incorrect. I should have written that we need a new function, pkix_IsCertSelfSigned, and that the code that i cited above, which now erroneously calls pkix_IsCertSelfIssued should call pkix_IsCertSelfSigned instead.

> CAI -> CAII -> CAII(Self-Issued) -> EE Why do we need to support such chains? Under what situations should that chain verify but neither of the following chains should verify? CAII(Self-Issued) -> EE CAI -> CAII -> EE

Self Issued means only that the subject and issuer names are the same. It does not necessitate that the cert is self-signed. The self issued cert have have a different key, and keyID, than the cert of its issuer, even though the names are the same. Self-Issued CA certs are used as "rollover" certs, to facilitate a transition from an old CA public key to a new one. Imagine that CAII(2k) is a new cert for CAII, with a 2k-bit pub key. Imagine that CAII(1k) is a new cert for the old public key previously used by CAII, a key of only 1k bits. Imagine that EE is signed with a 1k bit pub key. Then the chain CAI(4k) -> CAII(2k) -> CAII(1k) -> EE should validate, but CAII(1k) -> EE does not because CAII(1k) is not a trust anchor, and CAI(4k) -> CAII(2k) -> EE does not because EE was signed with a 1k bit key.

Nelson, thank you for the excellent explanation. Is it true, then, that the old non-libpkix cert chain building code cannot handle these self-issued certificates correctly either? AFAICT, given a chain like CAI(4k) -> CAII(2k) -> CAII(1k) -> EE, the older code would try to build a chain like CAII(2k) -> EE if CAII(2k) is newer than CAII(1k) and that would fail. If my assumption is correct, we can remove this from the blocking "libpkix by default in Firefox" bug.

The old çode should handle self-issued certificates correctly provided that the certs all correctly use SubjectKeyID and AuthorityKeyID extensions correctly, regardless of date.

Would this function need to actually perform the signature validation, or is that handled elsewhere? i.e., does pkix_isCertSelfSigned need to check to see that it actually is self-signed, or only that it should be?

In the past I've been told: CERTCertificate.isRoot -> bool, tells whether or not a cert is self signed We use this check in PSM when we need to know. If I understand correctly, we simply need to change libpkix to check this bool?

(In reply to Nelson Bolyard (seldom reads bugmail) from comment #6) > In comment 3, I wrote: > > That means that pkix_IsCertSelfIssued needs to be fixed before this bug > > can be fixed. > > That was incorrect. I should have written that we need a new function, > pkix_IsCertSelfSigned, and that the code that i cited above, which now > erroneously calls pkix_IsCertSelfIssued should call pkix_IsCertSelfSigned > instead. But the code you had quoted in comment 3 doesn't call pkix_IsCertSelfIssued, so it's not clear which call should be replaced.

Sorry, but I don't understand this bug report. Nelson said: "When function pkix_Build_VerifyCertificate comes to a self-signed root CA cert that is not trusted, it incorrectly determines that the chain has a loop. " I cannot see such a check. The only loop decision that I can find in pkix_Build_VerifyCertificate happens, if a candidate cert is already found in the chain that was built so far, and hence, would now be used again. And the only check that involves calling IsCertSelfIssued is related to a decision to delay revocation checking.

just in case it's still needed, here is a proposed implementation of pkix_IsCertSelfSigned