438685 - libpkix doesn't try all the issuers in a bridge with multiple certs

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Christophe Ravel]

When a Bridge has 3 or more issuers, libpkix tries only the first 2 issuers to build the cert chain

More details to come.

Comment 1

[Christophe Ravel]

PKI Configuration:

   ROOT_1  ROOT_2  ROOT_3 
         \    |   /
         BRIDGE_1_1
              |
             CA1
              |
             EE1

Comment 2

[Christophe Ravel]

Attachment: Certs used for the PKI configuration

Root certs:
ROOT_1Root.der: ROOT_1 self signed cert
ROOT_2Root.der: ROOT_2 self signed cert
ROOT_3Root.der: ROOT_3 self signed cert

Bridge certs:
ROOT_1BRIDGE_1_1cert.der: ROOT_1 issued cert for BRIDGE_1_1
ROOT_2BRIDGE_1_1cert.der: ROOT_2 issued cert for BRIDGE_1_1
ROOT_3BRIDGE_1_1cert.der: ROOT_3 issued cert for BRIDGE_1_1

Intermediate CA cert:
BRIDGE_1_1CA1cert.der: BRIDGE_1_1 issued cert for CA1

End entity cert:
CA1EE1cert.der: CA1 issued cert for EE1

Comment 3

[Christophe Ravel]

Tests that demonstrate the bug:

We are using VFYCHAIN for this test, and all the certs in attachement #1.


Verify cert chain for EE1, trust anchor = ROOT_1

$ vfychain -pp -v CA1EE1cert.der BRIDGE_1_1CA1cert.der ROOT_1BRIDGE_1_1cert.der ROOT_2BRIDGE_1_1cert.der ROOT_3BRIDGE_1_1cert.der -t ROOT_1Root.der
Chain is good!
Root Certificate Subject:: "CN=ROOT_1 ROOT CA,O=ROOT_1,C=US"
Certificate 1 Subject: "CN=EE1 EE,O=CA1,C=US"
Certificate 2 Subject: "CN=CA1 INTERMEDIATE,O=CA1,C=US"
Certificate 3 Subject: "CN=BRIDGE_1_1 BRIDGE,O=BRIDGE_1_1,C=US"


Verify cert chain for EE1, trust anchor = ROOT_2

$ vfychain -pp -v CA1EE1cert.der BRIDGE_1_1CA1cert.der ROOT_1BRIDGE_1_1cert.der ROOT_2BRIDGE_1_1cert.der ROOT_3BRIDGE_1_1cert.der -t ROOT_2Root.der
Chain is good!
Root Certificate Subject:: "CN=ROOT_2 ROOT CA,O=ROOT_2,C=US"
Certificate 1 Subject: "CN=EE1 EE,O=CA1,C=US"
Certificate 2 Subject: "CN=CA1 INTERMEDIATE,O=CA1,C=US"
Certificate 3 Subject: "CN=BRIDGE_1_1 BRIDGE,O=BRIDGE_1_1,C=US"


Verify cert chain for EE1, trust anchor = ROOT_3

$ vfychain -pp -v CA1EE1cert.der BRIDGE_1_1CA1cert.der ROOT_1BRIDGE_1_1cert.der ROOT_2BRIDGE_1_1cert.der ROOT_3BRIDGE_1_1cert.der -t ROOT_3Root.der
Chain is bad, -8179 = Peer's Certificate issuer is not recognized.

Comment 4

[Christophe Ravel]

With debugging traces:

$ export NSPR_LOG_MODULES="pkix:5"
$ export NSS_STRICT_SHUTDOWN="x"


$ $BIN_DIR/vfychain -pp -v CA1EE1cert.der BRIDGE_1_1CA1cert.der ROOT_1BRIDGE_1_1cert.der ROOT_2BRIDGE_1_1cert.der ROOT_3BRIDGE_1_1cert.der -t ROOT_3Root.der
1[44ef0]: ====> pkix_BuildForwardDepthFirstSearch calling pkix_Build_VerifyCertificate
1[44ef0]: ====> cert: [
        Version:         v3
        SerialNumber:    0089ed1688
        Issuer:          CN=BRIDGE_1_1 BRIDGE,O=BRIDGE_1_1,C=US
        Subject:         CN=CA1 INTERMEDIATE,O=CA1,C=US
        Validity: [From: Wed Jun 11, 2008
                   To:   Tue Jun 11, 2013]
        SubjectAltNames: (null)
        AuthorityKeyId:  (null)
        SubjectKeyId:    (null)
        SubjPubKeyAlgId: PKCS #1 RSA Encryption
        CritExtOIDs:     (2.5.29.19)
        ExtKeyUsages:    (null)
        BasicConstraint: CA(-1)
        CertPolicyInfo:  (null)
        PolicyMappings:  (null)
        ExplicitPolicy:  -1
        InhibitMapping:  -1
        InhibitAnyPolicy:-1
        NameConstraints: (null)
        AuthorityInfoAccess: (null)
        SubjectInfoAccess: (null)
        CacheFlag:       1
]

1[44ef0]: ====> pkix_BuildForwardDepthFirstSearch calling pkix_Build_VerifyCertificate
1[44ef0]: ====> cert: [
        Version:         v3
        SerialNumber:    0089ed167f
        Issuer:          CN=ROOT_1 ROOT CA,O=ROOT_1,C=US
        Subject:         CN=BRIDGE_1_1 BRIDGE,O=BRIDGE_1_1,C=US
        Validity: [From: Wed Jun 11, 2008
                   To:   Tue Jun 11, 2013]
        SubjectAltNames: (ROOT_1Root@ROOT_1)
        AuthorityKeyId:  (null)
        SubjectKeyId:    (null)
        SubjPubKeyAlgId: PKCS #1 RSA Encryption
        CritExtOIDs:     (2.5.29.19)
        ExtKeyUsages:    (null)
        BasicConstraint: CA(-1)
        CertPolicyInfo:  (null)
        PolicyMappings:  (null)
        ExplicitPolicy:  -1
        InhibitMapping:  -1
        InhibitAnyPolicy:-1
        NameConstraints: (null)
        AuthorityInfoAccess: (null)
        SubjectInfoAccess: (null)
        CacheFlag:       1
]

1[44ef0]: ====> pkix_BuildForwardDepthFirstSearch calling pkix_Build_VerifyCertificate
1[44ef0]: ====> cert: [
        Version:         v3
        SerialNumber:    0089ed167f
        Issuer:          CN=ROOT_1 ROOT CA,O=ROOT_1,C=US
        Subject:         CN=BRIDGE_1_1 BRIDGE,O=BRIDGE_1_1,C=US
        Validity: [From: Wed Jun 11, 2008
                   To:   Tue Jun 11, 2013]
        SubjectAltNames: (ROOT_1Root@ROOT_1)
        AuthorityKeyId:  (null)
        SubjectKeyId:    (null)
        SubjPubKeyAlgId: PKCS #1 RSA Encryption
        CritExtOIDs:     (2.5.29.19)
        ExtKeyUsages:    (null)
        BasicConstraint: CA(-1)
        CertPolicyInfo:  (null)
        PolicyMappings:  (null)
        ExplicitPolicy:  -1
        InhibitMapping:  -1
        InhibitAnyPolicy:-1
        NameConstraints: (null)
        AuthorityInfoAccess: (null)
        SubjectInfoAccess: (null)
        CacheFlag:       1
]

1[44ef0]: ====> pkix_BuildForwardDepthFirstSearch calling pkix_Build_VerifyCertificate
1[44ef0]: ====> cert: [
        Version:         v3
        SerialNumber:    0089ed1680
        Issuer:          CN=ROOT_2 ROOT CA,O=ROOT_2,C=US
        Subject:         CN=BRIDGE_1_1 BRIDGE,O=BRIDGE_1_1,C=US
        Validity: [From: Wed Jun 11, 2008
                   To:   Tue Jun 11, 2013]
        SubjectAltNames: (ROOT_2Root@ROOT_2)
        AuthorityKeyId:  (null)
        SubjectKeyId:    (null)
        SubjPubKeyAlgId: PKCS #1 RSA Encryption
        CritExtOIDs:     (2.5.29.19)
        ExtKeyUsages:    (null)
        BasicConstraint: CA(-1)
        CertPolicyInfo:  (null)
        PolicyMappings:  (null)
        ExplicitPolicy:  -1
        InhibitMapping:  -1
        InhibitAnyPolicy:-1
        NameConstraints: (null)
        AuthorityInfoAccess: (null)
        SubjectInfoAccess: (null)
        CacheFlag:       1
]

1[44ef0]: ====> [(pkix_BuildForwardDepthFirstSearch (&nbioContext, &state, &valResult, plContext))] failed: pkix_BuildForwardDepthFirstSearch failed
1[44ef0]: ====> [(pkix_Build_InitiateBuildChain (procParams, &nbioContext, &state, &buildResult, pVerifyNode, plContext))] failed: pkix_Build_InitiateBuildChain failed
1[44ef0]: Error at level 0: pkix_Build_InitiateBuildChain failed
1[44ef0]: Error at level 1: pkix_BuildForwardDepthFirstSearch failed
1[44ef0]: Error at level 2: Nss legacy err code: build failed. Issuer is unknown.
Chain is bad, -8179 = Peer's Certificate issuer is not recognized.

Comment 5

[Christophe Ravel]

Debugging traces for a case that works (trust anchor = ROOT_2):

$ $BIN_DIR/vfychain -pp -v CA1EE1cert.der BRIDGE_1_1CA1cert.der ROOT_1BRIDGE_1_1cert.der ROOT_2BRIDGE_1_1cert.der ROOT_3BRIDGE_1_1cert.der -t ROOT_2Root.der
1[44ef0]: ====> pkix_BuildForwardDepthFirstSearch calling pkix_Build_VerifyCertificate
1[44ef0]: ====> cert: [
        Version:         v3
        SerialNumber:    0089ed1688
        Issuer:          CN=BRIDGE_1_1 BRIDGE,O=BRIDGE_1_1,C=US
        Subject:         CN=CA1 INTERMEDIATE,O=CA1,C=US
        Validity: [From: Wed Jun 11, 2008
                   To:   Tue Jun 11, 2013]
        SubjectAltNames: (null)
        AuthorityKeyId:  (null)
        SubjectKeyId:    (null)
        SubjPubKeyAlgId: PKCS #1 RSA Encryption
        CritExtOIDs:     (2.5.29.19)
        ExtKeyUsages:    (null)
        BasicConstraint: CA(-1)
        CertPolicyInfo:  (null)
        PolicyMappings:  (null)
        ExplicitPolicy:  -1
        InhibitMapping:  -1
        InhibitAnyPolicy:-1
        NameConstraints: (null)
        AuthorityInfoAccess: (null)
        SubjectInfoAccess: (null)
        CacheFlag:       1
]

1[44ef0]: ====> pkix_BuildForwardDepthFirstSearch calling pkix_Build_VerifyCertificate
1[44ef0]: ====> cert: [
        Version:         v3
        SerialNumber:    0089ed167f
        Issuer:          CN=ROOT_1 ROOT CA,O=ROOT_1,C=US
        Subject:         CN=BRIDGE_1_1 BRIDGE,O=BRIDGE_1_1,C=US
        Validity: [From: Wed Jun 11, 2008
                   To:   Tue Jun 11, 2013]
        SubjectAltNames: (ROOT_1Root@ROOT_1)
        AuthorityKeyId:  (null)
        SubjectKeyId:    (null)
        SubjPubKeyAlgId: PKCS #1 RSA Encryption
        CritExtOIDs:     (2.5.29.19)
        ExtKeyUsages:    (null)
        BasicConstraint: CA(-1)
        CertPolicyInfo:  (null)
        PolicyMappings:  (null)
        ExplicitPolicy:  -1
        InhibitMapping:  -1
        InhibitAnyPolicy:-1
        NameConstraints: (null)
        AuthorityInfoAccess: (null)
        SubjectInfoAccess: (null)
        CacheFlag:       1
]

1[44ef0]: ====> pkix_BuildForwardDepthFirstSearch calling pkix_Build_VerifyCertificate
1[44ef0]: ====> cert: [
        Version:         v3
        SerialNumber:    0089ed167f
        Issuer:          CN=ROOT_1 ROOT CA,O=ROOT_1,C=US
        Subject:         CN=BRIDGE_1_1 BRIDGE,O=BRIDGE_1_1,C=US
        Validity: [From: Wed Jun 11, 2008
                   To:   Tue Jun 11, 2013]
        SubjectAltNames: (ROOT_1Root@ROOT_1)
        AuthorityKeyId:  (null)
        SubjectKeyId:    (null)
        SubjPubKeyAlgId: PKCS #1 RSA Encryption
        CritExtOIDs:     (2.5.29.19)
        ExtKeyUsages:    (null)
        BasicConstraint: CA(-1)
        CertPolicyInfo:  (null)
        PolicyMappings:  (null)
        ExplicitPolicy:  -1
        InhibitMapping:  -1
        InhibitAnyPolicy:-1
        NameConstraints: (null)
        AuthorityInfoAccess: (null)
        SubjectInfoAccess: (null)
        CacheFlag:       1
]

1[44ef0]: ====> pkix_BuildForwardDepthFirstSearch calling pkix_Build_VerifyCertificate
1[44ef0]: ====> cert: [
        Version:         v3
        SerialNumber:    0089ed1680
        Issuer:          CN=ROOT_2 ROOT CA,O=ROOT_2,C=US
        Subject:         CN=BRIDGE_1_1 BRIDGE,O=BRIDGE_1_1,C=US
        Validity: [From: Wed Jun 11, 2008
                   To:   Tue Jun 11, 2013]
        SubjectAltNames: (ROOT_2Root@ROOT_2)
        AuthorityKeyId:  (null)
        SubjectKeyId:    (null)
        SubjPubKeyAlgId: PKCS #1 RSA Encryption
        CritExtOIDs:     (2.5.29.19)
        ExtKeyUsages:    (null)
        BasicConstraint: CA(-1)
        CertPolicyInfo:  (null)
        PolicyMappings:  (null)
        ExplicitPolicy:  -1
        InhibitMapping:  -1
        InhibitAnyPolicy:-1
        NameConstraints: (null)
        AuthorityInfoAccess: (null)
        SubjectInfoAccess: (null)
        CacheFlag:       1
]

1[44ef0]: ====> pkix_CheckChain
1[44ef0]: ====> cert: [
        Version:         v3
        SerialNumber:    0089ed1680
        Issuer:          CN=ROOT_2 ROOT CA,O=ROOT_2,C=US
        Subject:         CN=BRIDGE_1_1 BRIDGE,O=BRIDGE_1_1,C=US
        Validity: [From: Wed Jun 11, 2008
                   To:   Tue Jun 11, 2013]
        SubjectAltNames: (ROOT_2Root@ROOT_2)
        AuthorityKeyId:  (null)
        SubjectKeyId:    (null)
        SubjPubKeyAlgId: PKCS #1 RSA Encryption
        CritExtOIDs:     (2.5.29.19)
        ExtKeyUsages:    (null)
        BasicConstraint: CA(-1)
        CertPolicyInfo:  (null)
        PolicyMappings:  (null)
        ExplicitPolicy:  -1
        InhibitMapping:  -1
        InhibitAnyPolicy:-1
        NameConstraints: (null)
        AuthorityInfoAccess: (null)
        SubjectInfoAccess: (null)
        CacheFlag:       1
]

1[44ef0]: ====> pkix_CheckChain
1[44ef0]: ====> cert: [
        Version:         v3
        SerialNumber:    0089ed1688
        Issuer:          CN=BRIDGE_1_1 BRIDGE,O=BRIDGE_1_1,C=US
        Subject:         CN=CA1 INTERMEDIATE,O=CA1,C=US
        Validity: [From: Wed Jun 11, 2008
                   To:   Tue Jun 11, 2013]
        SubjectAltNames: (null)
        AuthorityKeyId:  (null)
        SubjectKeyId:    (null)
        SubjPubKeyAlgId: PKCS #1 RSA Encryption
        CritExtOIDs:     (2.5.29.19)
        ExtKeyUsages:    (null)
        BasicConstraint: CA(-1)
        CertPolicyInfo:  (null)
        PolicyMappings:  (null)
        ExplicitPolicy:  -1
        InhibitMapping:  -1
        InhibitAnyPolicy:-1
        NameConstraints: (null)
        AuthorityInfoAccess: (null)
        SubjectInfoAccess: (null)
        CacheFlag:       1
]

1[44ef0]: ====> pkix_CheckChain
1[44ef0]: ====> cert: [
        Version:         v3
        SerialNumber:    0089ed168e
        Issuer:          CN=CA1 INTERMEDIATE,O=CA1,C=US
        Subject:         CN=EE1 EE,O=CA1,C=US
        Validity: [From: Wed Jun 11, 2008
                   To:   Tue Jun 11, 2013]
        SubjectAltNames: (null)
        AuthorityKeyId:  (null)
        SubjectKeyId:    (null)
        SubjPubKeyAlgId: PKCS #1 RSA Encryption
        CritExtOIDs:     (EMPTY)
        ExtKeyUsages:    (null)
        BasicConstraint: (null)
        CertPolicyInfo:  (null)
        PolicyMappings:  (null)
        ExplicitPolicy:  -1
        InhibitMapping:  -1
        InhibitAnyPolicy:-1
        NameConstraints: (null)
        AuthorityInfoAccess: (null)
        SubjectInfoAccess: (null)
        CacheFlag:       0
]

Chain is good!
Root Certificate Subject:: "CN=ROOT_2 ROOT CA,O=ROOT_2,C=US"
Certificate 1 Subject: "CN=EE1 EE,O=CA1,C=US"
Certificate 2 Subject: "CN=CA1 INTERMEDIATE,O=CA1,C=US"
Certificate 3 Subject: "CN=BRIDGE_1_1 BRIDGE,O=BRIDGE_1_1,C=US"

Comment 6

[Alexei Volkov]

Attachment: Patch v1 - fix sort implementation

Comment 7

[Alexei Volkov]

Comment on attachment 324991 [details] [diff] [review]
Patch v1 - fix sort implementation

Implementation of the bubble sort algorithm in libpkix starts with incoming list duplication. Later the original(not partially sorted) list was used to pick the next member of the list to sort.  As a result, in worst case scenario for the sort, then a list requires complete reordering(for example 4 3 2 1 => 1 2 3 4) the greater half of the original list was lost and substituted to a least half( 4 3 2 1 => 1 1 2 2). 

The patch fixes the problem.

Comment 8

[Alexei Volkov]

In libpkix, pkix_Build_GatherCerts get called to collect certs from available cert stores. pkix_Build_GatherCerts sorts collected certs by date and places older certs at the beginning of the list. The comment says that the step is done to improve the search for the path to a trust anchor. In my opinion the sorting step is unnecessary and does bring any performance wins. I propose to remove it.

Comment 9

[Nelson Bolyard (seldom reads bugmail)]

Actually, to be consistent with historic NSS behavior, it should sort certs
from newest to oldest, with newest first.  NSS wants to select the newest
valid cert from among the valid choices.

Comment 10

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 324991 [details] [diff] [review]
Patch v1 - fix sort implementation

This patch is good.  I'd like you also make one more change to this code.
(Please review this additional change.)
>                                PKIX_DECREF(leastObj);
>-                               PKIX_INCREF(cmpObj);
>                                leastObj = cmpObj;
>-                       }
>-
>-                       PKIX_DECREF(cmpObj);
>+                       } else 
>+                           PKIX_DECREF(cmpObj);
>                }

Comment 11

[Alexei Volkov]

attachment 324991 [details] [diff] [review] has been committed.

Comment 12

[Alexei Volkov]

Attachment: Patch v2 - reverse search sort result

Historically nss check newest cert first when building a chain. Preserve this behavior with this patch.

Comment 13

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 325007 [details] [diff] [review]
Patch v2 - reverse search sort result


>-        *pResult = result;
>+        *pResult = (result && PKIX_FALSE) || !(result && PKIX_TRUE);

What were you trying to achieve with that expression?!?   
That assignment is identical to:

          *pResult = !result;

Comment 14

[Christophe Ravel]

After updating NSS with this fix, the test that failed is now passing:

===============================================
Trust anchor: ROOT_3Root.der

-----------------------------------------------
vfychain -d EE1DB -pp -v CA1EE1cert.der BRIDGE_1_1CA1cert.der ROOT_1BRIDGE_1_1cert.der ROOT_2BRIDGE_1_1cert.der ROOT_3BRIDGE_1_1cert.der -t ROOT_3Root.der

Chain is good!
Root Certificate Subject:: "CN=ROOT_3 ROOT CA,O=ROOT_3,C=US"
Certificate 1 Subject: "CN=EE1 EE,O=CA1,C=US"
Certificate 2 Subject: "CN=CA1 INTERMEDIATE,O=CA1,C=US"
Certificate 3 Subject: "CN=BRIDGE_1_1 BRIDGE,O=BRIDGE_1_1,C=US"

RESULT: PASS
===============================================

Comment 15

[Alexei Volkov]

> What were you trying to achieve with that expression?!?   
> That assignment is identical to:
> 
>           *pResult = !result;
> 
Never mind. I was trying to archive something else. :)

Comment 16

[Alexei Volkov]

Attachment: Patch v3 - regression fix

Reverse the sort result - the latest cert goes first.

Additional fix to bubble sort implementation - the last patch brought regression: pointer to the last element in the list is unnecessary decrefed one more time at the end of the function, since the pointer to cmpObj was not set to NULL.

Comment 17

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 325593 [details] [diff] [review]
Patch v3 - regression fix

This patch is fine except for one part:

>                         } else {
>-                                PKIX_DECREF(cmpObj);
>+                            PKIX_DECREF(cmpObj);
>                         }

That indentation change makes this line have different 
indentation than the rest of the file.  Let's keep the 
indentation style consistent within the file, and leave
that one line the way it was.

Comment 18

[Alexei Volkov]

patch integrated