Closed Bug 438685 Opened 16 years ago Closed 16 years ago

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

Categories

(NSS :: Libraries, defect, P1)

Product:
NSS
Component:
Libraries
Version:
3.12
Type:
defect

Tracking

(Not tracked)

Status:
RESOLVED FIXED
Milestone:
3.12.1

People

(Reporter: christophe.ravel.bugs, Assigned: alvolkov.bgs)

Details

(Whiteboard: PKIX)

Attachments

(3 files, 1 obsolete file)

Certs used for the PKI configuration
4.77 KB, application/octet-stream
Details
Patch v1 - fix sort implementation
1.84 KB, patch
nelson
: review+
Details | Diff | Splinter Review
Patch v3 - regression fix
1.81 KB, patch
nelson
: review+
Details | Diff | Splinter Review 
When a Bridge has 3 or more issuers, libpkix tries only the first 2 issuers to build the cert chain

More details to come.
PKI Configuration:

   ROOT_1  ROOT_2  ROOT_3 
         \    |   /
         BRIDGE_1_1
              |
             CA1
              |
             EE1


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
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.
Assignee: nobody → alexei.volkov.bugs
Priority: -- → P1
Target Milestone: --- → 3.12.1
Whiteboard: PKIX
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.


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"



        Attachment #324991 -
        Flags: review?(nelson)

    
    

    
  
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.

    
    

    
  
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.

    
    

    
  
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 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);
>                }

        Attachment #324991 -
        Flags: review?(nelson) → review+

    
    

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

    
    

    
  


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

        Attachment #325007 -
        Flags: review?(nelson)

    
    

    
  
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;

        Attachment #325007 -
        Flags: review?(nelson) → review-

    
    

    
  
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
===============================================



    
  

        Attachment #325007 -
        Attachment is obsolete: true

    
    

    
  
> 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. :)


    
    

    
  


  
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.

        Attachment #325593 -
        Flags: review?(nelson)

    
    

    
  
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.

        Attachment #325593 -
        Flags: review?(nelson) → review+

    
    

    
  
patch integrated
Status: NEW → RESOLVED
Closed: 16 years ago
Resolution: --- → FIXED

          You need to log in
          before you can comment on or make changes to this bug.
        






  

    
  







  

    

      
Attachment

      

      
      
      
      
    

    

      

        

          

            
General

            

              Creator: 



            

            
Created: 

            
Updated: 

            
Size: