635384 - Stack overflow (infinite recursion) in PKIX_BuildChain when building certificate chain with a potential loop

Status: RESOLVED DUPLICATE of bug 551429

(NSS :: Libraries, defect, P1)

Description

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

+++ This bug was initially created as a clone of Bug #634074 +++

With NSS_ENABLE_PKIX_VERIFY=1, we get an infinite loop in pkix_BuildForwardDepthFirstSearch when attempting to access https://robin.eff.org in Firefox due to the issue with the certificates described in bug 634074 comment 6.

Comment 1

[Wan-Teh Chang]

Brian: thank you for doing the NSS_ENABLE_PKIX_VERIFY=1 experiment.

Could you test my "safety net" patch in bug 597618?  Does it prevent
the infinite loop?  (Note: my patch does not fix the underlying
cause of the infinite loop.)

Comment 2

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

No, that patch does not cause the loop to terminate. Firefox continually logs "(pkix_CacheCert_Add: PKIX_PL_HashTable_Add for Certs skipped: entry existed" just as without the patch.

Comment 3

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

Attachment: Stacktrace of stack overflow

It seems that (at least with that patch) we get an infinite recursion and crash:

 	nss3.dll!PKIX_BuildChain(PKIX_ProcessingParamsStruct * procParams=0x0ed5d7d0, void * * pNBIOContext=0x09f76b24, void * * pState=0x09f76aec, PKIX_BuildResultStruct * * pBuildResult=0x09f76af0, PKIX_VerifyNodeStruct * * pVerifyNode=0x09f76af4, void * plContext=0x0f637ae0)  Line 3748 + 0x1d bytes	C
 	nss3.dll!cert_BuildAndValidateChain(PKIX_ProcessingParamsStruct * procParams=0x0ed5d7d0, PKIX_BuildResultStruct * * pResult=0x09f76b40, PKIX_VerifyNodeStruct * * pVerifyNode=0x09f76b4c, void * plContext=0x0f637ae0)  Line 823 + 0x1d bytes	C
 	nss3.dll!cert_VerifyCertChainPkix(CERTCertificateStr * cert=0x082fa860, int checkSig=1, SECCertUsageEnum requiredUsage=certUsageAnyCA, __int64 time=1298356186000000, void * wincx=0x00000000, CERTVerifyLogStr * log=0x00000000, int * pSigerror=0x00000000, int * pRevoked=0x00000000)  Line 1267 + 0x15 bytes	C
 	nss3.dll!cert_VerifyCertChain(NSSTrustDomainStr * handle=0x07c09968, CERTCertificateStr * cert=0x082fa860, int checkSig=1, int * sigerror=0x00000000, SECCertUsageEnum certUsage=certUsageAnyCA, __int64 t=1298356186000000, void * wincx=0x00000000, CERTVerifyLogStr * log=0x00000000, int * revoked=0x00000000)  Line 883 + 0x29 bytes	C
 	nss3.dll!CERT_VerifyCertChain(NSSTrustDomainStr * handle=0x07c09968, CERTCertificateStr * cert=0x082fa860, int checkSig=1, SECCertUsageEnum certUsage=certUsageAnyCA, __int64 t=1298356186000000, void * wincx=0x00000000, CERTVerifyLogStr * log=0x00000000)  Line 895 + 0x29 bytes	C
 	nss3.dll!CERT_VerifyCert(NSSTrustDomainStr * handle=0x07c09968, CERTCertificateStr * cert=0x082fa860, int checkSig=1, SECCertUsageEnum certUsage=certUsageAnyCA, __int64 t=1298356186000000, void * wincx=0x00000000, CERTVerifyLogStr * log=0x00000000)  Line 1491 + 0x25 bytes	C
 	nss3.dll!pkix_pl_OcspResponse_VerifyResponse(PKIX_PL_OcspResponseStruct * response=0x0e65d198, PKIX_ProcessingParamsStruct * procParams=0x0ed5d740, SECCertUsageEnum certUsage=certUsageAnyCA, void * * state=0x09f76ca0, PKIX_BuildResultStruct * * buildResult=0x09f76ce8, void * * pNBIOContext=0x09f76c9c, void * plContext=0x0f633eb8)  Line 721 + 0x28 bytes	C
 	nss3.dll!pkix_pl_OcspResponse_VerifySignature(PKIX_PL_OcspResponseStruct * response=0x0e65d198, PKIX_PL_CertStruct * cert=0x0f53ec18, PKIX_ProcessingParamsStruct * procParams=0x0ed5d740, int * pPassed=0x09f76d24, void * * pNBIOContext=0x09f76d60, void * plContext=0x0f633eb8)  Line 900 + 0x28 bytes	C
 	nss3.dll!pkix_OcspChecker_CheckExternal(PKIX_PL_CertStruct * cert=0x0f53ec18, PKIX_PL_CertStruct * issuer=0x0f53ecf8, PKIX_PL_DateStruct * date=0x0f6366b8, pkix_RevocationMethodStruct * checkerObject=0x0f445310, PKIX_ProcessingParamsStruct * procParams=0x0ed5d740, unsigned int methodFlags=33, PKIX_RevocationStatusEnum * pRevStatus=0x09f76da8, unsigned int * pReasonCode=0x0ecf5890, void * * pNBIOContext=0x09f76e00, void * plContext=0x0f633eb8)  Line 328 + 0x1d bytes	C
 	nss3.dll!PKIX_RevocationChecker_Check(PKIX_PL_CertStruct * cert=0x0f53ec18, PKIX_PL_CertStruct * issuer=0x0f53ecf8, PKIX_RevocationCheckerStruct * revChecker=0x0f6584a0, PKIX_ProcessingParamsStruct * procParams=0x0ed5d740, int chainVerificationState=1, int testingLeafCert=1, PKIX_RevocationStatusEnum * pRevStatus=0x09f76e44, unsigned int * pReasonCode=0x0ecf5890, void * * pNbioContext=0x09f76e88, void * plContext=0x0f633eb8)  Line 431 + 0x30 bytes	C
 	nss3.dll!pkix_CheckChain(PKIX_ListStruct * certs=0x0f659280, unsigned int numCerts=2, PKIX_TrustAnchorStruct * anchor=0x0f6591c0, PKIX_ListStruct * checkers=0x0f659220, PKIX_RevocationCheckerStruct * revChecker=0x0f6584a0, PKIX_ListStruct * removeCheckedExtOIDs=0x0f659640, PKIX_ProcessingParamsStruct * procParams=0x0ed5d740, unsigned int * pCertCheckedIndex=0x0ecf587c, unsigned int * pCheckerIndex=0x0ecf5880, int * pRevChecking=0x0ecf58a0, unsigned int * pReasonCode=0x0ecf5890, void * * pNBIOContext=0x09f76f18, PKIX_PL_PublicKeyStruct * * pFinalSubjPubKey=0x09f76ee4, PKIX_PolicyNodeStruct * * pPolicyTree=0x09f76ee8, PKIX_VerifyNodeStruct * * pVerifyTree=0x00000000, void * plContext=0x0f633eb8)  Line 797 + 0x36 bytes	C
 	nss3.dll!pkix_Build_ValidateEntireChain(PKIX_ForwardBuilderStateStruct * state=0x0ecf5860, PKIX_TrustAnchorStruct * anchor=0x0f6591c0, void * * pNBIOContext=0x09f76f60, PKIX_ValidateResultStruct * * pValResult=0x09f76f84, PKIX_VerifyNodeStruct * verifyNode=0x0f658f80, void * plContext=0x0f633eb8)  Line 1348 + 0x64 bytes	C
 	nss3.dll!pkix_BuildForwardDepthFirstSearch(void * * pNBIOContext=0x09f77100, PKIX_ForwardBuilderStateStruct * state=0x0ecf5860, PKIX_ValidateResultStruct * * pValResult=0x09f770a8, void * plContext=0x0f633eb8)  Line 2567 + 0x23 bytes	C
 	nss3.dll!pkix_Build_InitiateBuildChain(PKIX_ProcessingParamsStruct * procParams=0x0ed5d740, void * * pNBIOContext=0x09f77174, PKIX_ForwardBuilderStateStruct * * pState=0x09f77144, PKIX_BuildResultStruct * * pBuildResult=0x09f77178, PKIX_VerifyNodeStruct * * pVerifyNode=0x09f771b4, void * plContext=0x0f633eb8)  Line 3575 + 0x18 bytes	C
 	nss3.dll!PKIX_BuildChain(PKIX_ProcessingParamsStruct * procParams=0x0ed5d740, void * * pNBIOContext=0x09f771e4, void * * pState=0x09f771ac, PKIX_BuildResultStruct * * pBuildResult=0x09f771b0, PKIX_VerifyNodeStruct * * pVerifyNode=0x09f771b4, void * plContext=0x0f633eb8)  Line 3748 + 0x1d bytes	C
 	nss3.dll!cert_BuildAndValidateChain(PKIX_ProcessingParamsStruct * procParams=0x0ed5d740, PKIX_BuildResultStruct * * pResult=0x09f77200, PKIX_VerifyNodeStruct * * pVerifyNode=0x09f7720c, void * plContext=0x0f633eb8)  Line 823 + 0x1d bytes	C
 	nss3.dll!cert_VerifyCertChainPkix(CERTCertificateStr * cert=0x08326000, int checkSig=1, SECCertUsageEnum requiredUsage=certUsageAnyCA, __int64 time=1298360646000000, void * wincx=0x00000000, CERTVerifyLogStr * log=0x00000000, int * pSigerror=0x00000000, int * pRevoked=0x00000000)  Line 1267 + 0x15 bytes	C
 	nss3.dll!cert_VerifyCertChain(NSSTrustDomainStr * handle=0x07c09968, CERTCertificateStr * cert=0x08326000, int checkSig=1, int * sigerror=0x00000000, SECCertUsageEnum certUsage=certUsageAnyCA, __int64 t=1298360646000000, void * wincx=0x00000000, CERTVerifyLogStr * log=0x00000000, int * revoked=0x00000000)  Line 883 + 0x29 bytes	C
 	nss3.dll!CERT_VerifyCertChain(NSSTrustDomainStr * handle=0x07c09968, CERTCertificateStr * cert=0x08326000, int checkSig=1, SECCertUsageEnum certUsage=certUsageAnyCA, __int64 t=1298360646000000, void * wincx=0x00000000, CERTVerifyLogStr * log=0x00000000)  Line 895 + 0x29 bytes	C
 	nss3.dll!CERT_VerifyCert(NSSTrustDomainStr * handle=0x07c09968, CERTCertificateStr * cert=0x08326000, int checkSig=1, SECCertUsageEnum certUsage=certUsageAnyCA, __int64 t=1298360646000000, void * wincx=0x00000000, CERTVerifyLogStr * log=0x00000000)  Line 1491 + 0x25 bytes	C
 	nss3.dll!pkix_pl_OcspResponse_VerifyResponse(PKIX_PL_OcspResponseStruct * response=0x0e65d110, PKIX_ProcessingParamsStruct * procParams=0x0ed5d6b0, SECCertUsageEnum certUsage=certUsageAnyCA, void * * state=0x09f77360, PKIX_BuildResultStruct * * buildResult=0x09f773a8, void * * pNBIOContext=0x09f7735c, void * plContext=0x0f635098)  Line 721 + 0x28 bytes	C
 	nss3.dll!pkix_pl_OcspResponse_VerifySignature(PKIX_PL_OcspResponseStruct * response=0x0e65d110, PKIX_PL_CertStruct * cert=0x0f53e6d8, PKIX_ProcessingParamsStruct * procParams=0x0ed5d6b0, int * pPassed=0x09f773e4, void * * pNBIOContext=0x09f77420, void * plContext=0x0f635098)  Line 900 + 0x28 bytes	C
 	nss3.dll!pkix_OcspChecker_CheckExternal(PKIX_PL_CertStruct * cert=0x0f53e6d8, PKIX_PL_CertStruct * issuer=0x0f53e7b8, PKIX_PL_DateStruct * date=0x0f631ac0, pkix_RevocationMethodStruct * checkerObject=0x0f444cf8, PKIX_ProcessingParamsStruct * procParams=0x0ed5d6b0, unsigned int methodFlags=33, PKIX_RevocationStatusEnum * pRevStatus=0x09f77468, unsigned int * pReasonCode=0x0ecf5660, void * * pNBIOContext=0x09f774c0, void * plContext=0x0f635098)  Line 328 + 0x1d bytes	C
 	nss3.dll!PKIX_RevocationChecker_Check(PKIX_PL_CertStruct * cert=0x0f53e6d8, PKIX_PL_CertStruct * issuer=0x0f53e7b8, PKIX_RevocationCheckerStruct * revChecker=0x0f656c40, PKIX_ProcessingParamsStruct * procParams=0x0ed5d6b0, int chainVerificationState=1, int testingLeafCert=1, PKIX_RevocationStatusEnum * pRevStatus=0x09f77504, unsigned int * pReasonCode=0x0ecf5660, void * * pNbioContext=0x09f77548, void * plContext=0x0f635098)  Line 431 + 0x30 bytes	C
 	nss3.dll!pkix_CheckChain(PKIX_ListStruct * certs=0x0f657ae0, unsigned int numCerts=2, PKIX_TrustAnchorStruct * anchor=0x0f657a20, PKIX_ListStruct * checkers=0x0f657a80, PKIX_RevocationCheckerStruct * revChecker=0x0f656c40, PKIX_ListStruct * removeCheckedExtOIDs=0x0f657ea0, PKIX_ProcessingParamsStruct * procParams=0x0ed5d6b0, unsigned int * pCertCheckedIndex=0x0ecf564c, unsigned int * pCheckerIndex=0x0ecf5650, int * pRevChecking=0x0ecf5670, unsigned int * pReasonCode=0x0ecf5660, void * * pNBIOContext=0x09f775d8, PKIX_PL_PublicKeyStruct * * pFinalSubjPubKey=0x09f775a4, PKIX_PolicyNodeStruct * * pPolicyTree=0x09f775a8, PKIX_VerifyNodeStruct * * pVerifyTree=0x00000000, void * plContext=0x0f635098)  Line 797 + 0x36 bytes	C
 	nss3.dll!pkix_Build_ValidateEntireChain(PKIX_ForwardBuilderStateStruct * state=0x0ecf5630, PKIX_TrustAnchorStruct * anchor=0x0f657a20, void * * pNBIOContext=0x09f77620, PKIX_ValidateResultStruct * * pValResult=0x09f77644, PKIX_VerifyNodeStruct * verifyNode=0x0f657840, void * plContext=0x0f635098)  Line 1348 + 0x64 bytes	C
 	nss3.dll!pkix_BuildForwardDepthFirstSearch(void * * pNBIOContext=0x09f777c0, PKIX_ForwardBuilderStateStruct * state=0x0ecf5630, PKIX_ValidateResultStruct * * pValResult=0x09f77768, void * plContext=0x0f635098)  Line 2567 + 0x23 bytes	C
 	nss3.dll!pkix_Build_InitiateBuildChain(PKIX_ProcessingParamsStruct * procParams=0x0ed5d6b0, void * * pNBIOContext=0x09f77834, PKIX_ForwardBuilderStateStruct * * pState=0x09f77804, PKIX_BuildResultStruct * * pBuildResult=0x09f77838, PKIX_VerifyNodeStruct * * pVerifyNode=0x09f77874, void * plContext=0x0f635098)  Line 3575 + 0x18 bytes	C
 	nss3.dll!PKIX_BuildChain(PKIX_ProcessingParamsStruct * procParams=0x0ed5d6b0, void * * pNBIOContext=0x09f778a4, void * * pState=0x09f7786c, PKIX_BuildResultStruct * * pBuildResult=0x09f77870, PKIX_VerifyNodeStruct * * pVerifyNode=0x09f77874, void * plContext=0x0f635098)  Line 3748 + 0x1d bytes	C

Comment 4

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

The stack overflow also occurs without the patch from bug 597618. Does this affect Firefox? I think that since these are EV-enabled roots, Firefox would hang and then crash for an EV-enabled site when this set of certs (as described in bug 634074 comment 6) are loaded in memory (e.g. by visiting sites that include the intermediate certs in their TLS cert chain).

Comment 5

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

See bug 551429, which may be the cause.

Comment 6

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

This occurs when CERT_SetUsePKIXForValidation(PR_TRUE) has been called to cause the libpkix-based implementation of CERT_VerifyCertChain to be used. If the old implementation of CERT_VerifyCertChain is used, the stack overflow won't occur. In particular, in Firefox with security.use_libpkix_verification=true, the stack overflow doesn't occur, unless we also have NSS_ENABLE_PKIX_VERIFY=1. 

I found bug 339737 which is about libpkix using CERT_VerifyCert internally and commented in bug 339737 comment 6. (That bug needs to be reopened but somehow I can't reopen it; please re-open it if you can.) I am not sure, but that bug might be at least partially responsible for this infinite looping.

Comment 7

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

The bug does not occur when we avoid NSS_ENABLE_PKIX_VERIFY=1 and/or disable OCSP in Firefox.