489714 - libPKIX erroneously detects cert chain loops when it finds untrusted roots

Status: RESOLVED WONTFIX

(NSS :: Libraries, defect, P1)

Description

[Nelson Bolyard (seldom reads bugmail)]

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.

Comment 1

[Nelson Bolyard (seldom reads bugmail)]

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

Comment 2

[Nelson Bolyard (seldom reads bugmail)]

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.

Comment 3

[Nelson Bolyard (seldom reads bugmail)]

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

Comment 4

[Alexei Volkov]

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.

Comment 5

[Nelson Bolyard (seldom reads bugmail)]

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.

Comment 6

[Nelson Bolyard (seldom reads bugmail)]

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.

Comment 7

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

> 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

Comment 8

[Nelson Bolyard (seldom reads bugmail)]

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.

Comment 9

[Brian Smith (:briansmith, :bsmith, use NEEDINFO?)]

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.

Comment 10

[Nelson Bolyard (seldom reads bugmail)]

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

Comment 11

[Kyle Hamilton]

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?

Comment 12

[Kai Engert (:KaiE:)]

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?

Comment 13

[Kai Engert (:KaiE:)]

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

Comment 14

[Kai Engert (:KaiE:)]

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.

Comment 15

[Kai Engert (:KaiE:)]

Attachment: implement pkix_IsCertSelfSigned

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