597618 - workaround: short-curcuit infinite loop in pkix_BuildForwardDepthFirstSearch when verifying the https://etime1.jt3.com/ server certificate with AIA certificate fetch enabled

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P2)

Description

[Wan-Teh Chang]

This is the bug I mentioned in the NSS conference call this week.
After I looked into it, I found that it is not specific to AIA
certificate download using LDAP.  HTTP certificate download has
the same bug.  But it seems to be related to cross certificates.

Steps to reproduce:

1. Apply the NSS patch in bug 528743 to ignore unknown AIA location
types.

2. Edit mozilla/security/nss/lib/libpkix/pkix_pl_nss/module/pkix_pl_aiamgr.c	and comment out the following code in PKIX_PL_AIAMgr_GetAIACerts so that
libpkix will not use LDAP to download certificates:

                 } else if (iaType == PKIX_INFOACCESS_LOCATION_LDAP) {
 			PKIX_CHECK(pkix_pl_AIAMgr_GetLDAPCerts
 				(aiaMgr, ia, &nbio, &certs, plContext),
 				PKIX_AIAMGRGETLDAPCERTSFAILED);

3. Use CERT_PKIXVerifyCert to verify the server certificate for
https://etime1.jt3.com/, with AIA certificate fetch enabled.

You will see that the while loop in pkix_BuildForwardDepthFirstSearch
does not terminate.

Comment 1

[Wan-Teh Chang]

Attachment: Safety net: max loop iteration count for pkix_BuildForwardDepthFirstSearch

I debugged this infinite loop for a full day today but
couldn't track this down.  For now I propose that we limit
that while loop to a maximum number of iterations to defend
against such bugs.

Comment 2

[Wan-Teh Chang]

Comment on attachment 476459 [details] [diff] [review]
Safety net: max loop iteration count for pkix_BuildForwardDepthFirstSearch

I forgot to mention that I also created a pkix_PrepareForwardBuilderStateForAIA
function for code that was duplicated in two places.  I also deleted several
unnecessary blank lines because the pkix_BuildForwardDepthFirstSearch function
is extremely long.

Comment 3

[Alexei Volkov]

Comment on attachment 476459 [details] [diff] [review]
Safety net: max loop iteration count for pkix_BuildForwardDepthFirstSearch

I think 250 a bit too much for chains we have today. Probably if it is more then a hundred it is already an indication that some thing is wrong.
r+

Comment 4

[Alexei Volkov]

Comment on attachment 476459 [details] [diff] [review]
Safety net: max loop iteration count for pkix_BuildForwardDepthFirstSearch

Requesting the second review. I'd like to see it in 3.12.10.

Comment 5

[Robert Relyea]

Comment on attachment 476459 [details] [diff] [review]
Safety net: max loop iteration count for pkix_BuildForwardDepthFirstSearch

r+ rrelyea

Comment 6

[Wan-Teh Chang]

Patch checked in on the NSS trunk (NSS 3.13) and the
NSS_3_12_BRANCH (NSS 3.12.10).

Checking in pkix_build.c;
/cvsroot/mozilla/security/nss/lib/libpkix/pkix/top/pkix_build.c,v  <--  pkix_bui
ld.c
new revision: 1.60; previous revision: 1.59
done

Checking in pkix_build.c;
/cvsroot/mozilla/security/nss/lib/libpkix/pkix/top/pkix_build.c,v  <--  pkix_bui
ld.c
new revision: 1.59.2.1; previous revision: 1.59
done

We're unlikely to have time to get to the bottom of
this soon, so I marked this bug FIXED even though I
only checked in a workaround.

Comment 7

[Wan-Teh Chang]

Attachment: Mark certs that have been tried as visited to prune DFS

I attach this patch to illustrate a possible solution
to this bug.

I spent two days looking into this bug.  I confirmed
what Alexei told me before, that libpkix does not go
into an infinite loop.  With AIA cert fetching, a total
of 78 certificates are considered by the cert path
building code, and this causes libpkix to stay in the
loop for many iterations.

Some of the certs have a high fan-out: I see 7 and 10.
Also, I see the chain length go as high as 16 or 17.

Possible solutions:

1. Limit the max chain length.

2. Limit the max fan-out.  This may require we assign good
scores to certs so we know which ones are more likely to
be useful in chain building.

3. Mark the certs that have been tried as visited to prune
the depth first search.  This is part of the standard depth
first search algorithm  This patch illustrates how this
solution can be implemented.  However, it is tricky to do
this safely.  The subtle issue is that although a cert is
unusable in one cert path (e.g., because the name constraint
or policy check fails), the cert may still be usable in other
cert paths.  So we can only mark a cert as visited if we
are sure it is futile to use the cert in any cert path.
One sufficient condition is that the cert cannot reach
any trusted cert.  (I believe libpkix only performs
policy and name constraint checks after reaching a trusted
cert.)  This patch implements this "trusted cert reached"
check partially.  I didn't check whether we can't reach
a trusted cert because of cert looping.

Without this patch, libpkix takes 318468 iterations in its
DFS to explore the graph of 78 certificates.

With this patch, libpkix takes 3068 iterations to finish DFS.

If I remove the !trustedCertReached check, then libpkix takes
263 iterations to finish DFS.  But I think this is risky if
policy or name constraint checks are performed.

Comment 8

[Wan-Teh Chang]

Attachment: ZIP file containing the test certificates

When unzipped, this ZIP file expands to a bug-597618 directory
containing the following certificates:

etime1_jt3_com.der: the SSL server certificate for etime1.jt3.com.

etime1_jt3_com_cert0.der - etime1_jt3_com_cert78.der: the certificates
that are downloaded from AIA cert fetching.

To reproduce this bug,

1. Edit mozilla/security/nss/lib/libpkix/pkix/top/pkix_build.c
and comment out the following code at the beginning of
the while loop in pkix_BuildForwardDepthFirstSearch:

            /*
             * The maximum number of iterations works around a bug that
             * causes this while loop to never exit when AIA and cross
             * certificates are involved.  See bug xxxxx.
             */
            if (numIterations++ > 250)
                    PKIX_ERROR(PKIX_TIMECONSUMEDEXCEEDSRESOURCELIMITS);

2. Write a test program that does the following:
- Import etime1_jt3_com_cert*.der (from 0 to 78) into NSS
  as temporary certs.
- Call CERT_PKIXVerifyCert to verify etime1_jt3_com.der,
  WITHOUT AIA cert fetching.