1112461 - libpkix incorrect prefers older, weaker certs over stronger, newer certs

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Ryan Sleevi]

libpkix incorrectly uses its Bubble Sort functionality when evaluating the relative weight of revocation checking mechanisms and when attempting to build certificate paths.

Rather than mirror Legacy or mozilla::pkix, both which prefer newer certificates over older certificates when multiple certificates match, libpkix has a logic bug that causes it to prefer older certificates.

The result of this is that it tends to select weaker chains (SHA-1, RSA-1024-bit), even when stronger chains exist - INCLUDING in the trust store.

I believe this logic bug is responsible for the disproportionate number of RSA-1024 bit validations that Chromium is seeing, as well as the root cause of NSS building SHA-1 chains as described in https://code.google.com/p/chromium/issues/detail?id=437733 / https://code.google.com/p/chromium/issues/detail?id=429824

Comment 1

[Ryan Sleevi]

Attachment: patch1.patch

Correct all uses of pkix_List_BubbleSort with proper comparators.

This fixes candidate cert sorting and revocation priority sorting.

Comment 2

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

Comment on attachment 8537625 [details] [diff] [review]
patch1.patch

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

Sorry, I'm not going to have time to work on this any time soon. Also, I'm no longer an NSS peer. Punting to Bob.

Comment 3

[Ryan Sleevi]

Bob: Can you review this?

Comment 4

[Wan-Teh Chang]

Comment on attachment 8537625 [details] [diff] [review]
patch1.patch

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

Ryan: after studying the code for an hour, I believe I fully understand
the bug and your proposed fix. Please fix the bug I spotted and evaluate
the suggested fix marked with "IMPORTANT". I also suggested some improvements
to the comments. Thanks.

An alternative approach is to change pkix_List_BubbleSort to sort in
descending order. I am not sure if that approach would be less confusing
though.

::: lib/libpkix/pkix/checker/pkix_revocationchecker.c
@@ +151,5 @@
>      
>      method1 = (pkix_RevocationMethod *)obj1;
>      method2 = (pkix_RevocationMethod *)obj2;
>      
> +    if (method1->priority < method2->priority) {

IMPORTANT: if the revocation methods should be sorted in descending order
(most preferred method at the front of the list), then we should also
invert the comparison in this function.

Since PKIX_RevocationChecker_Check tries the revocation methods from the
front of the list, I think this is the case.

@@ +153,5 @@
>      method2 = (pkix_RevocationMethod *)obj2;
>      
> +    if (method1->priority < method2->priority) {
> +      *pResult = -1;
> +    } else if (method2->priority > method1->priority) {

BUG: this test is equivalent to the first test, so it won't be
true. This test should be method1->priority > method2->priority.

This bug causes pkix_RevocationChecker_SortComparator to always
return a *pResult <= 0. As a result, pkix_List_BubbleSort leaves
the list unchanged.

::: lib/libpkix/pkix/top/pkix_build.c
@@ +686,1 @@
>  pkix_Build_SortCertComparator(

The description of this function says:
 * DESCRIPTION:
 *
 *  This Function takes two Certificates cast in "obj1" and "obj2",
 *  compares their validity NotAfter dates and returns the result at
 *  "pResult". The comparison key(s) can be expanded by using other
 *  data in the Certificate in the future.

We should improve the comment to say what "pResult" means, without
explicit reference to validity NotAfter dates. For example, we can
say "*pResult > 0 means obj1 is less desirable than obj2". We should
explain why the result seems flipped -- pkix_List_BubbleSort sorts
a list in ascending order. So to sort a list in descending order
using pkix_List_BubbleSort, we need to use a comparator callback
with a negative sense.

@@ +721,5 @@
>                  PKIX_CERTGETVALIDITYNOTAFTERFAILED);
>          
> +        /*
> +         * Prefer certificates with greater NotAfters by inverting the
> +         * comparison

Nit: this comment is confusing without pointing out that pkix_List_BubbleSort
sorts in ascending order, but the caller of this function wants to sort in
descending order, with the certs most likely to produce a successful chain at
the front of the list.

@@ +730,5 @@
>                  &result,
>                  plContext),
>                  PKIX_OBJECTCOMPARATORFAILED);
>  
> +        *pResult = result;

Another solution, which may be less confusing, is to flip the result here:

    PKIX_CHECK(PKIX_PL_Object_Compare
        ((PKIX_PL_Object *)date1,
        (PKIX_PL_Object *)date2,
        ...);

    /*
     * To make an ascending-order sorting function sort the list in descending
     * order, invert the comparison result.
     */
    *pResult = -result;

Comment 5

[Wan-Teh Chang]

Ryan: I think this bug means libpkix could be using the revocation methods
in the wrong order of priority, right?

Comment 6

[Ryan Sleevi]

Wan-Teh: Wow, thanks for spotting that bug. I'm going to look to see what can be done to better test that sorting.

Yes, the conclusion that I've reached is that the sorting is broken for revocation checking as well (when both methods are enabled).

Comment 7

[Ryan Sleevi]

Attachment: patch2.patch

Comment 8

[Wan-Teh Chang]

Comment on attachment 8546243 [details] [diff] [review]
patch2.patch

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

r=wtc. Please fix a typo in the comment in pkix_build.c.

This code is really hard to understand. I suggested some
comment changes to make the comments clearer to me. Feel
free to ignore those suggestions.

::: lib/libpkix/pkix/checker/pkix_revocationchecker.c
@@ +136,5 @@
>  
>          PKIX_RETURN(REVOCATIONCHECKER);
>  }
>  
> +/* Sort methods by their priorities (lower priority = higher preference) */

I verified this comment is correct. I found a comment that says
"0 corresponds to the highest priority", and NSS uses the index
of the preferred_methods array as the priority, consistent with
that comment.

::: lib/libpkix/pkix/top/pkix_build.c
@@ +662,5 @@
>   *  This Function takes two Certificates cast in "obj1" and "obj2",
> + *  compares them to determine which is a more preferable certificate
> + *  for chain building. This Function is suitable for use as a
> + *  comparator callback for pkix_List_BubbleSort, setting "*pResult" to
> + *  > 0 if "obj2" is more desirable than "obj1" and > 0 if "obj1"

Typo: The second "> 0" should be "< 0".

Nit: I find it easier to understand if this is written as follows:

                                       ...., setting "*pResult" to
  > 0 if "obj1" is less desirable than "obj2" and < 0 if "obj1"
  is more desirable than "obj2".

I made a similar suggestion below. I'll let you decide.

@@ +663,5 @@
> + *  compares them to determine which is a more preferable certificate
> + *  for chain building. This Function is suitable for use as a
> + *  comparator callback for pkix_List_BubbleSort, setting "*pResult" to
> + *  > 0 if "obj2" is more desirable than "obj1" and > 0 if "obj1"
> + *  is more desirable than "obj2".

Nit: explain the counter-intuitive comparison result, something like:
  The inverted result makes pkix_List_BubbleSort sort the certificates in
  descending order of desirability.

@@ +699,5 @@
>          PKIX_NULLCHECK_THREE(obj1, obj2, pResult);
>  
>          /*
>           * For sorting candidate certificates, we use NotAfter date as the
>           * sorted key for now (can be expanded if desired in the future).

Nit: sorted key => comparison key

@@ +730,5 @@
>                  PKIX_OBJECTCOMPARATORFAILED);
>  
> +        /*
> +         * Invert the result, so that if date2 is greater than date1,
> +         * obj2 is sorted before obj1. This is because pkix_List_BubbleSort

Nit: I find the first sentence easier to understand if we swap 1 and 2:

  Invert the result, so that if date1 is greater than date2,
  obj1 is sorted before obj2.

Comment 9

[Wan-Teh Chang]

Attachment: Improve a comment and fix comment nits

Comment 10

[Ryan Sleevi]

http://hg.mozilla.org/projects/nss/rev/34e1379ff6c7 (does not include wtc@'s comment updates)

Comment 11

[Wan-Teh Chang]

Comment on attachment 8546341 [details] [diff] [review]
Improve a comment and fix comment nits

https://hg.mozilla.org/projects/nss/rev/4a7112302401

Comment 12

[Kai Engert [:KaiE:]]

mass change target milestone to 3.17.4