479508 - unknown issuer errors result from cross certification loops or having multiple certs with the same ID or public key

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P2)

Description

[Nelson Bolyard (seldom reads bugmail)]

As reported in bug 477186, two of Mozilla's trusted root CAs have issued
cross certificates for each other.  Under various circumstances (to be 
detailed in a subsequent comment to this bug) this can cause NSS's old 
pre-libPKIX cert chain building code to go into a loop.  The loop is 
terminated after a finite number of repetitions, but the result is that 
the constructed chain does not terminate in a trust anchor, and so the 
final outcome of the cert chain verification is an unknown or untrusted 
issuer error.  See bug 477186 for steps to reproduce.

I suspect the only real solution to this is for PSM to switch to always 
use libPKIX.  Bug 479393 requests just that.  

Rob, A potentially enlightening experiment would be to run the very latest 
trunk FF + trunk NSS build with this environment variable set:

NSS_ENABLE_PKIX_VERIFY=1

Comment 1

[Nelson Bolyard (seldom reads bugmail)]

Here is an attempt to summarize the situation that Rob Stradling raised 
in bug 477186 and bug 479029.  It may also be related to bug 479231.

Among Mozilla's many self-signed root CA certs are two of immediate interest:

A) CN=UTN-USERFirst-Hardware,OU=http://www.usertrust.com,
   O=The USERTRUST Network,L=Salt Lake City,ST=UT,C=US
   Not Before: 1999-07-09 18:10:42 GMT

B) CN=AddTrust External CA Root,OU=AddTrust External TTP Network,
   O=AddTrust AB,C=SE
   Not Before: 2000-05-30 10:48:38 GMT

These two roots have issued certs to "cross certify" each other.
On the same date, UTN-USERFirst-Hardware (Abbr: UTN-UF-H) issued a cert
to AddTrust External CA Root (Abbr: AddTrust), and AddTrust's root issue
two certs for UTN-UF-H.  Both of those latter two certs have identical 
subject names, issuer names, subject keys, and validity periods.  They 
differ by serial number, by certain extensions (one has Cert Policies),
and (of course) signature.

In tabular form, we have 5 CA certs of interest:
  cert   Subject  Issuer   Date        Other
  ----   -------- -------- ----------  -------
   A     UTN-UF-H self     1999-07-09 
   B     AddTrust self     2000-05-30 
   1     UTN-UF-H AddTrust 2005-06-07  Policy
   2     UTN-UF-H AddTrust 2005-06-07 
   3     AddTrust UTN-UF-H 2005-06-07

NSS has two bodies of code that attempt to build and verify a cert chain.
We call them the "old" code and the "new" or "libPKIX" code. When 
validating an SSL server cert, Firefox uses the old code first, to answer 
the question: "Is this SSL server cert a valid SSL server cert?"  and then, it may use the new code in a second pass to answer the question: "Is this cert a valid EV cert?".  The old code is also used in building and 
verifying the cert chains on OCSP responses, and (IINM) CRLs.   The old 
code is also used to build the cert chain that is displayed when viewing
a cert chain in PSM's Certificate Manager windows.

This bug is interested in the behavior of the old code.  It builds a chain
from the leaf (server cert) towards the root.  At each step, it tries to 
find THE "best" issuer cert for the current cert under test.  Then it 
finds the "best" issuer for that cert, and so on, until it finds that the
"best" cert at some step is a trusted cert, or it comes to the end of a 
chain (e.g. a self-signed cert) that is not trusted.  To find the "best" 
issuer cert, it finds all certs whose subject name is the desired name,
that are within their validity periods, are CA certs, and whose subject
key IDs are the desired one (if applicable).  Those may include certs
that were received from the SSL server and also certs previously stored in 
the browser's cert DB.  Then, if more than one qualifies, it chooses the 
"newest" one, based on notBefore date.  If there is a multi-way tie for 
"newest", it chooses the one with the most distant future notAfter date, 
and if there is a tie for that, then it arbitrarily picks one first one it found (IIRC, or maybe it's the last one found, I don't recall, but it 
doesn't really matter).  At no time during this process of selecting the
"best" cert does "trust" come into play.  A cert is checked for being
trusted only AFTER it has been identified as the "best" issuer cert for
the preceding cert in the chain.  The old code pays no attention whatever
to cert policy extensions.  

Given a server cert R with issuer name AddTrust, one of these chains will 
be constructed by the old code, depending on what CA certs it has at hand:

R -> B				(if 3 is not present)
R -> 3 -> A			(if neither 1 nor 2 is present)
R -> 3 -> 1 -> 3 (loop)
R -> 3 -> 2 -> 3 (loop)

Given a server cert S with issuer name UTN-UF-H, one of these chains will 
be constructed by the old code, depending on what CA certs it has at hand:

S -> A 				(if neither 1 nor 2 is present)
S -> 1 -> B			(if 3 is not present)
S -> 2 -> B			(if 3 is not present)
S -> 1 -> 3 -> 1 (loop)
S -> 2 -> 3 -> 2 (loop)

Because certs 1 and 2 have identical validity periods, if both are present
then the one chosen will be dependent on the order in which they are found.

Loops are terminated when the total chain length reaches an arbitrary 
maximum length, currently 20 certs.  Such chains never include a trust 
anchor, and so are always found to be untrusted.

The old code builds ONE chain and tests it, and that's it.  It contains no
logic that tries to build a second alternative chain if the first one fails.  
In contrast to that, the new libPKIX code will do a full tree walk, if 
necessary, to find a cert chain that is valid.  

It would probably help if we changed the old code's algorithm for finding 
the "best" issuer cert to take trust into consideration, always choosing a 
trusted cert over an untrusted cert when presented with that choice.  

The other alternative is to change PSM to always use libPKIX, and stop 
using the "old" code.  libPKIX also has the ability to fetch missing CA
certs using URLs in AIA cert extensions, when called through the new 
libPKIX API.  However, that change is a PSM change, not an NSS change.  
I don't know when that change might be made, because it's not a change 
the NSS team can make.

I will investigate the possibility of considering trust when choosing 
the "best" issuer cert in the old code.

Comment 2

[Rob Stradling]

> Rob, A potentially enlightening experiment would be to run the very latest
> trunk FF + trunk NSS build with this environment variable set:
> NSS_ENABLE_PKIX_VERIFY=1

With trunk FF + trunk NSS + the patch from bug #479029 + NSS_ENABLE_PKIX_VERIFY=1, I can no longer reproduce any of the sec_error_ocsp_invalid_signing_cert or sec_error_unknown_issuer errors I reported in bug #479029.

However, I can still reproduce the 20-cert-long Certificate Hierarchy mentioned in Bug #479029 comment #16.

Even with Wan-Teh's patch from bug #479393 added to the mix, I still see the 20-cert-long Certificate Hierarchy.

Comment 3

[Nelson Bolyard (seldom reads bugmail)]

Thanks for your report in comment 2, Rob.  That environment variable is 
exactly equivalent to the patch in bug 479393.

I think there is already a bug filed about the fact that PSM uses the old
code to build the cert chain that it displays.  This has been a problem 
usually seen in the context of EV certs.  A search for EV and cert chains
or certificate manager should find it.

Comment 4

[Nelson Bolyard (seldom reads bugmail)]

Alexei rightly pointed out today that testing for trust in a cert loop will
only help if one of the certs in the loop is trusted.  In this case, it 
would help because each of the cross certs was issued directly by a trusted
root.  But if the cross certs had been issued by subordinate CAs, checking
for trust would not have helped at all.  :-/

Comment 5

[Nelson Bolyard (seldom reads bugmail)]

Attachment: incomplete patch - depends on missing function

This patch would solve the problem, IF the function 
NSSCertificate_IsTrustedForUsage(c, usage) 
existed, but it doesn't.  That is the subject of bug 482153.

Comment 7

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

As Bug 638730 shows, this is a more general problem; it isn't caused only by loops that would create an infinite chain.

Comment 8

[Nikolaus Demmel]

This bug just bit me yesterday when trying to figure out what the heck was going on with https://www.kth.se and others signed by "TERENA SSL CA". I'm experiencing the long trust chains between the two certificates mentioned in this bug and FF tells me the site is not trustd because the issuer of the cert would be unknown. This is on FF 6.0.2 OS X.
Interestingly this happens not quite deterministically on my OS X, FF 6 setup. Sometimes the chain is shorter and FF does not complain about the site being untrusted, but looking at the figerprints it still seems to use the wrong certificates. However I have not been able o reproduce this on other installtions of FF.
Is anyone working on this?

Comment 9

[Wan-Teh Chang]

Fixed by the patch in bug 764393 comment 29, which is based on Nelson's "incomplete patch".

Comment 10

[romain.uribes]

Hello,

I wanted to see if the problem was still current with an old version of firefox. I have not succeeded to reproduce the bug. Do you know if the problem can reproduce an old version of firefox? thank you

Comment 11

[Wan-Teh Chang]

Bug 764393 comment 29 shows this bug was fixed in NSS 3.13.6.
So you should be able to reproduce this bug with an old version
of Firefox that uses NSS 3.13.5 or older.