1020237 - (mozilla::pkix) BuildForward() should prefer a root certificate to a "newer" non-root certificate

Status: RESOLVED FIXED

(Core :: Security: PSM, defect)

Description

[Rob Stradling]

Attachment: Prefer a root certificate to a "newer" non-root certificate

Some (newer) BuiltIn root certificates are cross-certified by other (older) BuiltIn root certificates.  In some cases a cross-certificate has a more recent notBefore date than the associated root certificate, and in other cases the reverse is true.

Although mozilla::pkix "attempts all potential trust chains for a certificate before giving up" [1], it is likely to use a longer chain (in the cases where a cross-certificate has the most recent notBefore date) even when a shorter chain is available.

A longer chain means more certificate signatures to verify, additional OCSP lookups (for EV, at least), and therefore slower page loads.

So, I think mozilla::pkix should use the shortest valid chain up to a BuiltIn root certificate, at least when validating Server Authentication certificates.

The attached patch causes NSS's CERT_SortCBValidity() function to list a root certificate ahead of a non-root certificate that has a more recent notBefore date.  This has the desired effect for HTTPS: the shortest chain is selected (and displayed in the certificate viewer), and fewer OCSP lookups are performed.  However, I'm expecting r- on this patch, because I suspect that it would create problems in other contexts - e.g. when sending an S/MIME message, it's normally best to send the longest chain, because the recipient might need the cross-certificate (because they trust the legacy root certificate but not the newer root certificate).

Alternative approach: mozilla::pkix's BuildForward() function could re-sort the candidates list (just after it calls trustDomain.FindPotentialIssuers() and just before the loop that calls BuildForwardInner() ).  BuildForward() would only do this re-sorting when requiredKeyUsagesIfPresent, requiredEKUIfPresent and/or requiredPolicy indicate that the shortest chain is preferable.

Alternative approach 2: Let NSS expose a mechanism that would allow mozilla::pkix to specify which sorting function NSS should use.


[1] https://blog.mozilla.org/security/2014/04/24/exciting-updates-to-certificate-verification-in-gecko/

Comment 1

[Rob Stradling]

BTW, setting the environment variable "NSPR_LOG_MODULES=certverifier:4" proved to be very useful when I was investigating this issue.

Comment 2

[Rob Stradling]

Attachment: Example intermediate with newer notBefore than root

Example: Install the attached cross-certificate into your certificate store, then browse to https://secure.comodo.com.  The longer chain up to the "AddTrust External CA Root" BuiltIn is used, rather than the shorter chain up to the "COMODO Certification Authority" BuiltIn.
With the patch, the shorter chain is used instead.

Comment 3

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

Thanks for your patch, Rob.

I see your patch is a change to NSS. Please file a new bug in product:NSS component:libraries with your patch, and make this bug depend on that new bug.

Also, thanks for the example that demonstrates the issue. Could you write a unit test in the style of the security/pkix/test/gtest/pkix_cert_chain_length_tests.cpp test? AFAICT, it would require changing the CreateEncodedCertificate function in security/pkix/test/lib/pkixtestutil.[ch] so that it can optionally accept a keypair as input, so that it supports generating two certificates that share a keypair.

Note: This change won't result in us always choosing the shortest path, right? Instead, given the local choice between a non-root and a root certificate, it will choose the root certificate. Often, but not always, that will be the shortest path. 

Consider:
EE -> INT1 -> INT2 -> INT3 -> ROOT
EE -> INT4 -> ROOT

If we choose INT1 over INT4 to start with then we'll not build the EE -> INT4 -> ROOT path. Choosing the shortest path build require us to switch from depth-first search to breadth-first search, which I'd rather not do.

Still, I agree it makes sense to at least make the locally-optimum decision, so we should just update the summary of this bug to be more accurate.

Comment 4

[Rob Stradling]

(In reply to Brian Smith from comment #3)
<snip>
> I see your patch is a change to NSS. Please file a new bug in product:NSS
> component:libraries with your patch, and make this bug depend on that new
> bug.

I just filed bug 1021015.

> Also, thanks for the example that demonstrates the issue. Could you write a
> unit test in the style of the
> security/pkix/test/gtest/pkix_cert_chain_length_tests.cpp test?
<snip>

I'll have a go.

> Note: This change won't result in us always choosing the shortest path,
> right? Instead, given the local choice between a non-root and a root
> certificate, it will choose the root certificate. Often, but not always,
> that will be the shortest path.

Yeah, that's right.

<snip>
> Still, I agree it makes sense to at least make the locally-optimum decision,
> so we should just update the summary of this bug to be more accurate.

OK.

Comment 5

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

I believe this problem is probably easier to fix with the latest mozilla::pkix code, because we don't depend so much on NSS's selection logic and we can customize it within mozilla::pkix however we want. If this is still an issue then it would be great to get a patch (from you, or somebody else) to process the results from CERT_CreateSubjectCertList in a way that prefers roots.

Comment 6

[Rob Stradling]

Attachment: FindIssuer_PreferRoots.patch

(In reply to Brian Smith (:briansmith, :bsmith, use NEEDINFO?) from comment #5)
> ...it would be great to get a patch (from you, or somebody else) to process
> the results from CERT_CreateSubjectCertList in a way that prefers roots.

Brian, sorry for the delay.  New patch attached.

Comment 7

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

Comment on attachment 8516681 [details] [diff] [review]
FindIssuer_PreferRoots.patch

Review of attachment 8516681 [details] [diff] [review]:
-----------------------------------------------------------------

Rob, although I asked you to change basically every line of this patch, I do think the overall idea of your patch is good. Could you please update the patch based on my comments? Let me know if I've overlooked something or if I've made a suggestion you disagree with.

::: security/certverifier/NSSCertDBTrustDomain.cpp
@@ +114,5 @@
>    ScopedCERTCertList
>      candidates(CERT_CreateSubjectCertList(nullptr, CERT_GetDefaultCertDB(),
>                                            &encodedIssuerNameSECItem, 0,
>                                            false));
>    if (candidates) {

Please add a comment here like "First, try all the root certs; then try all the non-root certs."

@@ +115,5 @@
>      candidates(CERT_CreateSubjectCertList(nullptr, CERT_GetDefaultCertDB(),
>                                            &encodedIssuerNameSECItem, 0,
>                                            false));
>    if (candidates) {
> +    bool checkValidRootsOnly = true;

This variable name makes sends for the first time through, but not for the second. Perhaps "isRoot" would be a better name, since then you can write n->cert->isRoot == isRoot.

@@ +126,5 @@
> +          n = CERT_LIST_HEAD(candidates);
> +        }
> +        else
> +          break;
> +      }

Please write this like:

if (CERT_LIST_END(n, candidates)) {
  if (!isRoot) {
    // We already looped through all root certs and
    // all non-non-root certs; we're done.
    break;
  }
  // Now, go through the list again, looking at the
  // non-root certs.
  checkValidRootsOnly = false;
  n = CERT_LIST_HEAD(candidates);
}

Rationale:

1. If we're going to "break" or "return", we prefer to do so ASAP, according to the Gecko coding style.

2. We always put braces around single-line control statements, and your "else break" is missing the braces.

@@ +132,5 @@
> +          (!n->cert->isRoot ||
> +            (CERT_CheckCertValidTimes(n->cert, PR_Now(), PR_FALSE)
> +              != secCertTimeValid))) {
> +        continue;
> +      }

You can just write this:

if (n->cert->isRoot != isRoot) {
  continue;
}

Reasoning:

1. In the second time through the list, there's no reason to try the root certs, since we already know that none of them are good. But, in your patch, you first try all root certs, and then you go through the non-root AND root certs, so each root cert is potentially tried twice.

2. You don't need to call CERT_CheckCertValidTimes because the call to IsValid below will check that (nearly) right away.

3. Calling CERT_CheckCertValidTimes is not right because mozilla::pkix has its own logic for determining the cert validity, and the result of CERT_CheckCertValidTimes may not match it.

Comment 8

[Rob Stradling]

Attachment: FindIssuer_PreferRoots_v2.patch

(In reply to Brian Smith (:briansmith, :bsmith, use NEEDINFO?) from comment #7)
<snip>
> Rob, although I asked you to change basically every line of this patch, I do
> think the overall idea of your patch is good. Could you please update the
> patch based on my comments? Let me know if I've overlooked something or if
> I've made a suggestion you disagree with.

Brian, thanks for that review.  Patch v2 addresses all of your comments.

Just one very minor nit...

<snip>
> Please write this like:
> 
> if (CERT_LIST_END(n, candidates)) {
>   if (!isRoot) {
>     // We already looped through all root certs and
>     // all non-non-root certs; we're done.

Typo: s/non-non-/non-/

Also, to fit it on one line I reduced that comment to...
  // We already looped through all root and non-root certs; we're done.

Comment 9

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

Comment on attachment 8517413 [details] [diff] [review]
FindIssuer_PreferRoots_v2.patch

Review of attachment 8517413 [details] [diff] [review]:
-----------------------------------------------------------------

r+ with comment addressed.

::: security/certverifier/NSSCertDBTrustDomain.cpp
@@ +126,5 @@
> +          break;
> +        }
> +        // Now, go through the list again, looking at the non-root certs.
> +        isRoot = false;
> +        n = CERT_LIST_HEAD(candidates);

Here you need to add:

if (CERT_LIST_END(n, candidates)) {
  break; // can only happen if candidates is empty
}

Sorry I didn't catch this earlier.

Comment 10

[Rob Stradling]

Attachment: FindIssuer_PreferRoots_v3a.patch

(In reply to Brian Smith (:briansmith, :bsmith, use NEEDINFO?) from comment #9)
<snip>
> r+ with comment addressed.
<snip>
> Here you need to add:
> 
> if (CERT_LIST_END(n, candidates)) {
>   break; // can only happen if candidates is empty
> }

Good catch!

Patch v3a attached.

Comment 11

[Rob Stradling]

Attachment: FindIssuer_PreferRoots_v3b.patch

(In reply to Brian Smith (:briansmith, :bsmith, use NEEDINFO?) from comment #7)
<snip>
> 1. If we're going to "break" or "return", we prefer to do so ASAP, according
> to the Gecko coding style.

Brian, you might prefer this alternative patch (v3b).

Please check-in (or request super-review for?) v3a or v3b, whichever you prefer.

Thanks.

Comment 12

[Rob Stradling]

Brian, would you be able to commit either the v3a or v3b patch this week?

IIUC, that would be the timeframe for getting this into FF36 (which would be really nice!)

Thanks.

Comment 13

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

Comment on attachment 8518895 [details] [diff] [review]
FindIssuer_PreferRoots_v3a.patch

Review of attachment 8518895 [details] [diff] [review]:
-----------------------------------------------------------------

Rob, I prefer this version because I prefer return values to always be explicitly checked, instead of relying on implicit invariants, whenever is practical. Hoewver, I agree that the other version of your patch makes sense too.

David, please make sure there's nothing objectionable about this to you. If there isn't, then please check it in.

Comment 14

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

Comment on attachment 8518898 [details] [diff] [review]
FindIssuer_PreferRoots_v3b.patch

See my previous comment. I like the other version better.

Comment 15

[Dana Keeler (she/her) (use needinfo) [:keeler]]

Attachment: alternate implementation (this is the patch that landed)

I don't have a problem with changing the behavior of NSSCertDBTrustDomain in this way, but I'm concerned that the implementation in attachment 8518895 [details] [diff] [review] makes FindIssuer difficult to understand. In particular, using a single for loop to iterate over a data structure twice is uncommon and unexpected. Here's an alternate implementation that factors out the common inner code and makes it more obvious that the list is operated on twice.
I verified this by hand by following the instructions in comment 2.

Comment 16

[Rob Stradling]

Comment on attachment 8526927 [details] [diff] [review]
alternate implementation (this is the patch that landed)

Thanks David.  LGTM.

Comment 17

[Rob Stradling]

Comment on attachment 8526927 [details] [diff] [review]
alternate implementation (this is the patch that landed)

Thanks Brian.

David, can your patch be checked in now?

Comment 18

[Dana Keeler (she/her) (use needinfo) [:keeler]]

Thanks for the feedback and review.

https://hg.mozilla.org/integration/mozilla-inbound/rev/73051c757857

Comment 19

[Nigel Babu [:nigelb]]

Hi, there's a build bustage from this patch. I've closed the trees, can you take a look? Remember to land the fix with CLOSED TREE in the commit message.

Comment 20

[Dana Keeler (she/her) (use needinfo) [:keeler]]

Thanks, Nigel. I'm about to push a fix.

Comment 21

[Dana Keeler (she/her) (use needinfo) [:keeler]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/9cdb1871bd65

Comment 22

[Nigel Babu [:nigelb]]

Thank you, tree re-opened :)

Comment 23

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/73051c757857
https://hg.mozilla.org/mozilla-central/rev/9cdb1871bd65