chain.c

Go to the documentation of this file.

/****************************************************************************
*                                                                           *
*                     Certificate Chain Management Routines                 *
*                       Copyright Peter Gutmann 1996-2008                   *
*                                                                           *
****************************************************************************/

#if defined( INC_ALL ) 
  #include "cert.h"
  #include "asn1.h"
  #include "asn1_ext.h"
  #include "misc_rw.h"
#else
  #include "cert/cert.h"
  #include "enc_dec/asn1.h"
  #include "enc_dec/asn1_ext.h"
  #include "enc_dec/misc_rw.h"
#endif /* Compiler-specific includes */

/* When matching by subjectKeyIdentifier we don't use values less than 40
   bits because some CAs use monotonically increasing sequence numbers for 
   the sKID, which can clash with the same values when used by other CAs */

#define MIN_SKID_SIZE   5

/* A structure for storing pointers to parent and child (issuer and subject)
   names, key identifiers, and serial numbers (for finding a certificate by 
   issuerAndSerialNumber) and one for storing pointers to chaining 
   information */

typedef struct {
    BUFFER_FIXED( issuerDNsize ) \
    const void *issuerDN;
    BUFFER_FIXED( subjectDNsize ) \
    const void *subjectDN;
    int issuerDNsize, subjectDNsize;
    BUFFER_FIXED( serialNumberSize ) \
    const void *serialNumber;
    int serialNumberSize;
    BUFFER_OPT_FIXED( subjectKeyIDsize ) \
    const void *subjectKeyIdentifier;
    int subjectKeyIDsize;
#ifdef USE_CERTLEVEL_PKIX_PARTIAL
    BUFFER_OPT_FIXED( issuerKeyIDsize ) \
    const void *issuerKeyIdentifier;
    int issuerKeyIDsize;
#endif /* USE_CERTLEVEL_PKIX_PARTIAL */
    } CHAIN_INFO;

typedef struct {
    BUFFER_FIXED( DNsize ) \
    const void *DN;
    int DNsize;
#ifdef USE_CERTLEVEL_PKIX_PARTIAL
    BUFFER_FIXED( keyIDsize ) \
    const void *keyIdentifier;
    int keyIDsize;
#endif /* USE_CERTLEVEL_PKIX_PARTIAL */
    } CHAINING_INFO;

/* Match an identifier in a chain information structure against a chaining 
   information structure */

#define matchDN( chainingInfo, chainInfo, type ) \
        ( ( chainingInfo )->DNsize > 0 && \
          ( chainingInfo )->DNsize == ( chainInfo )->type##DNsize && \
          !memcmp( ( chainingInfo )->DN, ( chainInfo )->type##DN, \
                   ( chainInfo )->type##DNsize ) )

#define matchKeyID( chainingInfo, chainInfo, type ) \
        ( ( chainingInfo )->keyIDsize > MIN_SKID_SIZE && \
          ( chainingInfo )->keyIDsize == ( chainInfo )->type##KeyIDsize && \
          !memcmp( ( chainingInfo )->keyIdentifier, \
                   ( chainInfo )->type##KeyIdentifier, \
                   ( chainInfo )->type##KeyIDsize ) )

#ifdef USE_CERTIFICATES

/****************************************************************************
*                                                                           *
*                               Utility Routines                            *
*                                                                           *
****************************************************************************/

/* Copy subject or issuer chaining values from the chaining information */

STDC_NONNULL_ARG( ( 1, 2 ) ) \
static void getSubjectChainingInfo( OUT CHAINING_INFO *chainingInfo,
                                    const CHAIN_INFO *chainInfo )
    {
    assert( isWritePtr( chainingInfo, sizeof( CHAINING_INFO ) ) );
    assert( isReadPtr( chainInfo, sizeof( CHAIN_INFO ) ) );

    memset( chainingInfo, 0, sizeof( CHAINING_INFO ) );
    chainingInfo->DN = chainInfo->subjectDN;
    chainingInfo->DNsize = chainInfo->subjectDNsize;
#ifdef USE_CERTLEVEL_PKIX_PARTIAL
    chainingInfo->keyIdentifier = chainInfo->subjectKeyIdentifier;
    chainingInfo->keyIDsize = chainInfo->subjectKeyIDsize;
#endif /* USE_CERTLEVEL_PKIX_PARTIAL */
    }

STDC_NONNULL_ARG( ( 1, 2 ) ) \
static void getIssuerChainingInfo( OUT CHAINING_INFO *chainingInfo,
                                   const CHAIN_INFO *chainInfo )
    {
    assert( isWritePtr( chainingInfo, sizeof( CHAINING_INFO ) ) );
    assert( isReadPtr( chainInfo, sizeof( CHAIN_INFO ) ) );

    memset( chainingInfo, 0, sizeof( CHAINING_INFO ) );
    chainingInfo->DN = chainInfo->issuerDN;
    chainingInfo->DNsize = chainInfo->issuerDNsize;
#ifdef USE_CERTLEVEL_PKIX_PARTIAL
    chainingInfo->keyIdentifier = chainInfo->issuerKeyIdentifier;
    chainingInfo->keyIDsize = chainInfo->issuerKeyIDsize;
#endif /* USE_CERTLEVEL_PKIX_PARTIAL */
    }

/* Determine whether a given certificate is the subject or issuer for the 
   requested certificate based on the chaining information.  We chain by 
   issuer DN if possible but if that fails we use the keyID.  This is 
   somewhat dodgy since it can lead to the situation where a certificate 
   supposedly issued by Verisign Class 1 Public Primary Certification 
   Authority is actually issued by Honest Joe's Used Cars but the standard 
   requires this as a fallback (PKIX section 4.2.1.1).
   
   There are actually two different interpretations of chaining by keyID, 
   the first says that the keyID is a non-DN identifier that can survive 
   operations such as cross-certification and re-parenting so that if a 
   straight chain by DN fails then a chain by keyID is possible as a 
   fallback option.  The second is that the keyID is a disambiguator if 
   multiple paths in a chain-by-DN scenario are present in a spaghetti PKI.  
   Since the latter is rather unlikely to occur in a standard PKCS #7/SSL 
   certificate chain (half the implementations around wouldn't be able to 
   assemble the chain any more) we use the former interpretation by default 
   but enable the latter if useStrictChaining is set.
   
   If useStrictChaining is enabled we require that the DN *and* the keyID 
   match, which (even without a spaghetti PKI being in effect) is required 
   to handle PKIX weirdness in which multiple potential issuers can be 
   present in a chain due to CA certificate renewals/reparenting.  We don't 
   do this by default because too many CAs get keyID chaining wrong, leading 
   to apparent breaks in the chain when the keyID fails to match.
   
   We don't have to worry about strict chaining for the issuer match because
   we only use it when we're walking down the chain looking for a leaf 
   certificate */

CHECK_RETVAL_BOOL STDC_NONNULL_ARG( ( 1, 2 ) ) \
static BOOLEAN isSubject( const CHAINING_INFO *chainingInfo,
                          const CHAIN_INFO *chainInfo,
                          const BOOLEAN useStrictChaining )
    {
    BOOLEAN dnChains = FALSE, keyIDchains = FALSE;

    assert( isReadPtr( chainingInfo, sizeof( CHAINING_INFO ) ) );
    assert( isReadPtr( chainInfo, sizeof( CHAIN_INFO ) ) );

    /* Check for chaining by DN and keyID */
    if( matchDN( chainingInfo, chainInfo, subject ) )
        dnChains = TRUE;
#ifdef USE_CERTLEVEL_PKIX_PARTIAL
    if( matchKeyID( chainingInfo, chainInfo, subject ) )
        keyIDchains = TRUE;
#endif /* USE_CERTLEVEL_PKIX_PARTIAL */

    /* If we're using strict chaining both the DN and the keyID must chain */
    if( useStrictChaining )
        return( dnChains && keyIDchains );

    /* We're not using strict chaining, either can chain */
    return( dnChains || keyIDchains );
    }

CHECK_RETVAL_BOOL STDC_NONNULL_ARG( ( 1, 2 ) ) \
static BOOLEAN isIssuer( const CHAINING_INFO *chainingInfo,
                         const CHAIN_INFO *chainInfo )
    {
    assert( isReadPtr( chainingInfo, sizeof( CHAINING_INFO ) ) );
    assert( isReadPtr( chainInfo, sizeof( CHAIN_INFO ) ) );

    /* In the simplest case we chain by name.  This works for almost all
       certificates */
    if( matchDN( chainingInfo, chainInfo, issuer ) )
        return( TRUE );

#ifdef USE_CERTLEVEL_PKIX_PARTIAL
    /* If that fails we chain by keyID */
    if( matchKeyID( chainingInfo, chainInfo, issuer ) )
        return( TRUE );
#endif /* USE_CERTLEVEL_PKIX_PARTIAL */

    return( FALSE );
    }

/* Get the location and size of certificate attribute data required for
   chaining */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 3, 4 ) ) \
static int getChainingAttribute( INOUT CERT_INFO *certInfoPtr,
                                 IN_ATTRIBUTE \
                                    const CRYPT_ATTRIBUTE_TYPE attributeType,
                                 OUT_BUFFER_ALLOC_OPT( *attributeLength ) \
                                    const void **attributePtrPtr, 
                                 OUT_LENGTH_SHORT_Z int *attributeLength )
    {
    ATTRIBUTE_PTR *attributePtr;

    assert( isWritePtr( certInfoPtr, sizeof( CERT_INFO ) ) );
    assert( isReadPtr( attributePtrPtr, sizeof( void * ) ) );
    assert( isWritePtr( attributeLength, sizeof( int * ) ) );

    ENSURES( attributeType == CRYPT_CERTINFO_SUBJECTKEYIDENTIFIER || \
             attributeType == CRYPT_CERTINFO_AUTHORITY_KEYIDENTIFIER );

    /* Clear return values */
    *attributePtrPtr = NULL;
    *attributeLength = 0;

    /* Find the requested attribute and return a pointer to it */
    attributePtr = findAttributeField( certInfoPtr->attributes,
                                       attributeType, CRYPT_ATTRIBUTE_NONE );
    if( attributePtr == NULL )
        {
        /* If the chaining attribute data isn't present this isn't an 
           error */
        return( CRYPT_OK );
        }
    return( getAttributeDataPtr( attributePtr, ( void ** ) attributePtrPtr, 
                                 attributeLength ) );
    }

/* Free a certificate chain */

STDC_NONNULL_ARG( ( 1 ) ) \
static void freeCertChain( IN_ARRAY( certChainSize ) \
                                CRYPT_CERTIFICATE *iCertChain,
                           IN_RANGE( 1, MAX_CHAINLENGTH ) \
                                const int certChainSize )
    {
    int i;

    assert( isWritePtr( iCertChain, sizeof( CRYPT_CERTIFICATE ) * certChainSize ) );

    REQUIRES_V( certChainSize > 0 && certChainSize <= MAX_CHAINLENGTH );

    for( i = 0; i < certChainSize && i < MAX_CHAINLENGTH; i++ )
        {
        krnlSendNotifier( iCertChain[ i ], IMESSAGE_DESTROY );
        iCertChain[ i ] = CRYPT_ERROR;
        }
    }

/****************************************************************************
*                                                                           *
*                           Build a Certificate Chain                       *
*                                                                           *
****************************************************************************/

/* Build up the parent/child pointers for a certificate chain */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2 ) ) \
static int buildChainInfo( OUT_ARRAY( certChainSize ) CHAIN_INFO *chainInfo,
                           IN_ARRAY( certChainSize ) \
                                const CRYPT_CERTIFICATE *iCertChain,
                           IN_RANGE( 1, MAX_CHAINLENGTH ) \
                                const int certChainSize )
    {
    int i;

    assert( isWritePtr( chainInfo, sizeof( CHAIN_INFO ) * certChainSize ) );
    assert( isReadPtr( iCertChain, sizeof( CRYPT_CERTIFICATE ) * certChainSize ) );

    REQUIRES( certChainSize > 0 && certChainSize <= MAX_CHAINLENGTH );

    /* Clear return value */
    memset( chainInfo, 0, sizeof( CHAIN_INFO ) * certChainSize );

    /* Extract the subject and issuer DNs and key identifiers from each
       certificate.  Maintaining an external pointer into the internal
       structure is safe since the objects are reference-counted and won't be
       destroyed until the encapsulating certificate is destroyed */
    for( i = 0; i < certChainSize && i < MAX_CHAINLENGTH; i++ )
        {
        CERT_INFO *certChainPtr;
        int status;

        status = krnlAcquireObject( iCertChain[ i ], OBJECT_TYPE_CERTIFICATE, 
                                    ( void ** ) &certChainPtr, 
                                    CRYPT_ERROR_SIGNALLED );
        if( cryptStatusError( status ) )
            return( status );
        ANALYSER_HINT( certChainPtr != NULL );
        chainInfo[ i ].subjectDN = certChainPtr->subjectDNptr;
        chainInfo[ i ].subjectDNsize = certChainPtr->subjectDNsize;
        chainInfo[ i ].issuerDN = certChainPtr->issuerDNptr;
        chainInfo[ i ].issuerDNsize = certChainPtr->issuerDNsize;
        chainInfo[ i ].serialNumber = certChainPtr->cCertCert->serialNumber;
        chainInfo[ i ].serialNumberSize = certChainPtr->cCertCert->serialNumberLength;
        status = getChainingAttribute( certChainPtr, 
                                       CRYPT_CERTINFO_SUBJECTKEYIDENTIFIER,
                                       &chainInfo[ i ].subjectKeyIdentifier,
                                       &chainInfo[ i ].subjectKeyIDsize );
        if( cryptStatusError( status ) )
            {
            krnlReleaseObject( certChainPtr->objectHandle );
            return( status );
            }
#ifdef USE_CERTLEVEL_PKIX_PARTIAL
        status = getChainingAttribute( certChainPtr, 
                                       CRYPT_CERTINFO_AUTHORITY_KEYIDENTIFIER,
                                       &chainInfo[ i ].issuerKeyIdentifier,
                                       &chainInfo[ i ].issuerKeyIDsize );
        if( cryptStatusError( status ) )
            {
            krnlReleaseObject( certChainPtr->objectHandle );
            return( status );
            }
#endif /* USE_CERTLEVEL_PKIX_PARTIAL */
        krnlReleaseObject( certChainPtr->objectHandle );
        }
    ENSURES( i < MAX_CHAINLENGTH );

    return( CRYPT_OK );
    }

/* Find the leaf node in a (possibly unordered) certificate chain by walking 
   down the chain as far as possible.  The strategy we use is to pick an 
   initial certificate (which is often the leaf certificate anyway) and keep 
   looking for certificates it (or its successors) have issued until we 
   reach the end of the chain.  Returns the position of the leaf node in the 
   chain */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
static int findLeafNode( IN_ARRAY( certChainSize ) const CHAIN_INFO *chainInfo,
                         IN_RANGE( 1, MAX_CHAINLENGTH ) const int certChainSize )
    {
    CHAINING_INFO chainingInfo;
    BOOLEAN certUsed[ MAX_CHAINLENGTH + 8 ], moreMatches;
    int lastCertPos, iterationCount;

    assert( isReadPtr( chainInfo, sizeof( CHAIN_INFO ) * certChainSize ) );

    REQUIRES( certChainSize > 0 && certChainSize <= MAX_CHAINLENGTH );

    /* We start our search at the first certificate, which is often the leaf 
       certificate anyway */
    memset( certUsed, 0, MAX_CHAINLENGTH * sizeof( BOOLEAN ) );
    getSubjectChainingInfo( &chainingInfo, &chainInfo[ 0 ] );
    certUsed[ 0 ] = TRUE;
    lastCertPos = 0;

    /* Walk down the chain from the currently selected certificate checking 
       for certificates issued by it until we can't go any further.  Note 
       that this algorithm handles chains with PKIX path-kludge certificates 
       as well as normal ones since it marks a certificate as used once it 
       processes it for the first time, avoiding potential endless loops on 
       subject == issuer path-kludge certificates */
    for( moreMatches = TRUE, iterationCount = 0;
         moreMatches && iterationCount < MAX_CHAINLENGTH;
         iterationCount++ )
        {
        int i;

        /* We don't have a match until we discover otherwise */
        moreMatches = FALSE;

        /* Try and find a certificate issued by the current certificate */
        for( i = 0; i < certChainSize && i < MAX_CHAINLENGTH; i++ )
            {
            /* If there's another certificate below the current one in the 
               chain, mark the current one as used and move on to the next 
               one */
            if( !certUsed[ i ] && \
                isIssuer( &chainingInfo, &chainInfo[ i ] ) )
                {
                getSubjectChainingInfo( &chainingInfo, &chainInfo[ i ] );
                certUsed[ i ] = TRUE;
                moreMatches = TRUE;
                lastCertPos = i;
                break;
                }
            }
        ENSURES( i < MAX_CHAINLENGTH );
        }
    ENSURES( iterationCount < MAX_CHAINLENGTH );

    return( lastCertPos );
    }

/* Find a leaf node as identified by issuerAndSerialNumber or 
   subjectKeyIdentifier.  Returns the position of the leaf node in the 
   chain */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 4 ) ) \
static int findIdentifiedLeafNode( IN_ARRAY( certChainSize ) \
                                        const CHAIN_INFO *chainInfo,
                                   IN_RANGE( 1, MAX_CHAINLENGTH ) \
                                        const int certChainSize,
                                   IN_KEYID const CRYPT_KEYID_TYPE keyIDtype,
                                   IN_BUFFER( keyIDlength ) const void *keyID, 
                                   IN_LENGTH_KEYID const int keyIDlength )
    {
    STREAM stream;
    void *serialNumber = DUMMY_INIT_PTR, *issuerDNptr = DUMMY_INIT_PTR;
    int issuerDNsize, serialNumberSize;
    int i, status;

    assert( isReadPtr( chainInfo, sizeof( CHAIN_INFO ) * certChainSize ) );
    assert( isReadPtr( keyID, keyIDlength ) );

    REQUIRES( certChainSize > 0 && certChainSize <= MAX_CHAINLENGTH );
    REQUIRES( keyIDtype == CRYPT_IKEYID_KEYID || \
              keyIDtype == CRYPT_IKEYID_ISSUERANDSERIALNUMBER );
    REQUIRES( keyID != NULL && \
              keyIDlength >= MIN_SKID_SIZE && \
              keyIDlength < MAX_ATTRIBUTE_SIZE );

    /* If it's a subjectKeyIdentifier walk down the chain looking for a
       match */
    if( keyIDtype == CRYPT_IKEYID_KEYID )
        {
        for( i = 0; i < certChainSize && i < MAX_CHAINLENGTH; i++ )
            {
            if( chainInfo[ i ].subjectKeyIDsize > MIN_SKID_SIZE && \
                chainInfo[ i ].subjectKeyIDsize == keyIDlength && \
                !memcmp( chainInfo[ i ].subjectKeyIdentifier, keyID,
                         keyIDlength ) )
                return( i );
            }
        ENSURES( i < MAX_CHAINLENGTH );
        return( CRYPT_ERROR_NOTFOUND );
        }

    /* It's an issuerAndSerialNumber, extract the issuer DN and serial 
       number */
    sMemConnect( &stream, keyID, keyIDlength );
    readSequence( &stream, NULL );
    status = getStreamObjectLength( &stream, &issuerDNsize );
    if( cryptStatusOK( status ) )
        status = sMemGetDataBlock( &stream, &issuerDNptr, issuerDNsize );
    if( cryptStatusError( status ) )
        {
        sMemDisconnect( &stream );
        return( CRYPT_ERROR_NOTFOUND );
        }
    sSkip( &stream, issuerDNsize );             /* Issuer DN */
    status = readGenericHole( &stream, &serialNumberSize, 1, BER_INTEGER );
    if( cryptStatusOK( status ) )               /* Serial number */
        status = sMemGetDataBlock( &stream, &serialNumber, 
                                   serialNumberSize );
    sMemDisconnect( &stream );
    if( cryptStatusError( status ) )
        return( CRYPT_ERROR_NOTFOUND );
    ANALYSER_HINT( issuerDNptr != NULL );
    ANALYSER_HINT( serialNumber != NULL );

    /* Walk down the chain looking for the one identified by the 
       issuerAndSerialNumber */
    for( i = 0; i < certChainSize && i < MAX_CHAINLENGTH; i++ )
        {
        if( chainInfo[ i ].issuerDNsize > 0 && \
            chainInfo[ i ].issuerDNsize == issuerDNsize && \
            !memcmp( chainInfo[ i ].issuerDN, issuerDNptr,
                     issuerDNsize ) && \
            compareSerialNumber( chainInfo[ i ].serialNumber, 
                                 chainInfo[ i ].serialNumberSize,
                                 serialNumber, serialNumberSize ) )
            return( i );
        }
    ENSURES( i < MAX_CHAINLENGTH );

    return( CRYPT_ERROR_NOTFOUND );
    }

/* Sort the issuer certificates in a certificate chain, discarding any 
   unnecessary certificates.  If we're canonicalising an existing chain then 
   the start point in the chain is given by certChainStart and the -1th 
   certificate is the end user certificate and isn't part of the ordering 
   process.  If we're building a new chain from an arbitrary set of 
   certificates then the start point is given by the chaining information 
   for the leaf certificate.

   The canonicalisation of the chain can be handled in one of two ways, the 
   logical way and the PKIX way.  The latter allows apparently self-signed
   certificates in the middle of a chain due to certificate 
   renewals/reparenting, which completely breaks the standard certificate 
   convention that a self-signed certificate is a root CA.  This means that 
   without special handling the chain will terminate at a certificate that 
   appears to be (but isn't) the CA root certificate.  A sample chain of 
   this form (in this case involving an oldWithNew certificate) is as 
   follows:

    Issuer      Subject     Key/sKID    Sig/aKID
    ------      -------     --------    ----------
    Root        CA          ca_new      root
    CA          CA          ca_old      ca_new
    CA          EE          ee          ca_old

   In order to handle these chains we need to match by both DN *and* keyID,
   however since so many CAs get keyIDs wrong enabling this by default 
   would break many certificate chains.  To handle this we only enable the 
   extra-match behaviour if the compliance level is 
   CRYPT_COMPLIANCELEVEL_PKIX_FULL, for which people should be expecting all 
   sorts of bizarre behaviour anyway */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2, 3 ) ) \
static int sortCertChain( INOUT_ARRAY( certChainSize ) CRYPT_CERTIFICATE *iCertChain,
                          OUT_RANGE( 0, MAX_CHAINLENGTH ) int *orderedCertChainSize,
                          IN_ARRAY( certChainSize ) const CHAIN_INFO *chainInfo,
                          IN_RANGE( 1, MAX_CHAINLENGTH ) const int certChainSize,
                          IN_RANGE( 1, MAX_CHAINLENGTH ) const int leafCertEntry,
                          IN_HANDLE_OPT const CRYPT_CERTIFICATE certChainStart,
                          IN_OPT const CHAINING_INFO *chainingInfo,
                          const BOOLEAN useStrictChaining )
    {
    CRYPT_CERTIFICATE orderedChain[ MAX_CHAINLENGTH + 8 ];
    CHAINING_INFO localChainingInfo;
    BOOLEAN chainInfoValid[ MAX_CHAINLENGTH + 8 ], moreMatches;
    const int maxMatchLevel = useStrictChaining ? 1 : 0;
    int orderedChainIndex, iterationCount, i;

    assert( isWritePtr( iCertChain, sizeof( CRYPT_CERTIFICATE ) * certChainSize ) );
    assert( isReadPtr( chainInfo, sizeof( CHAIN_INFO ) * certChainSize ) );
    assert( ( isHandleRangeValid( certChainStart ) && \
              chainingInfo == NULL ) || \
            ( certChainStart == CRYPT_UNUSED && \
              isReadPtr( chainingInfo, sizeof( CHAINING_INFO ) ) ) );

    REQUIRES( certChainSize > 0 && certChainSize <= MAX_CHAINLENGTH );
    REQUIRES( leafCertEntry >= 0 && leafCertEntry <= certChainSize );
    REQUIRES( ( isHandleRangeValid( certChainStart ) && \
                chainingInfo == NULL ) || \
              ( certChainStart == CRYPT_UNUSED && \
                chainingInfo != NULL ) );

    /* Clear return value */
    *orderedCertChainSize = 0;

    /* Initially all chain entries except the one for the leaf certificate 
       are valid */
    for( i = 0; i < certChainSize && i < MAX_CHAINLENGTH; i++ )
        chainInfoValid[ i ] = TRUE;
    ENSURES( i < MAX_CHAINLENGTH );
    chainInfoValid[ leafCertEntry ] = FALSE;

    /* If we're canonicalising an existing chain there's a predefined chain
       start that we copy over and prepare to look for the next certificate 
       up the chain */
    if( certChainStart != CRYPT_UNUSED )
        {
        getIssuerChainingInfo( &localChainingInfo, &chainInfo[ 0 ] );
        orderedChain[ 0 ] = certChainStart;
        chainInfoValid[ 0 ] = FALSE;
        orderedChainIndex = 1;
        }
    else
        {
        /* We're building a new chain, the caller has supplied the chaining
           information */
        memcpy( &localChainingInfo, chainingInfo, sizeof( CHAINING_INFO ) );
        orderedChainIndex = 0;
        }

    /* Build an ordered chain of certificates from the leaf to the root */
    for( moreMatches = TRUE, iterationCount = 0;
         moreMatches && iterationCount < FAILSAFE_ITERATIONS_MED;
         iterationCount++ )
        {
        int matchLevel;

        /* We don't have a match until we discover otherwise */
        moreMatches = FALSE;

        /* Find the certificate with the current issuer as its subject.  If 
           we're using strict chaining we first try a strict match 
           (matchLevel = TRUE), if that fails we fall back to a standard 
           match (matchLevel = FALSE).  This is required to handle the
           significant number of CAs that don't get chaining by keyID 
           right */
        for( matchLevel = maxMatchLevel; \
             !moreMatches && matchLevel >= 0; matchLevel-- )
            {
            for( i = 0; i < certChainSize && i < MAX_CHAINLENGTH; i++ )
                {
                /* If this isn't the issuer, continue */
                if( !chainInfoValid[ i ] || \
                    !isSubject( &localChainingInfo, &chainInfo[ i ], 
                                matchLevel ) )
                    continue;

                /* We've found the issuer, move the certificate to the 
                   ordered chain and prepare to find its issuer */
                orderedChain[ orderedChainIndex++ ] = iCertChain[ i ];
                getIssuerChainingInfo( &localChainingInfo, &chainInfo[ i ] );
                chainInfoValid[ i ] = FALSE;
                moreMatches = TRUE; /* Exit outer loop as well */
                break;
                }
            ENSURES( i < MAX_CHAINLENGTH );
            }
        ENSURES( orderedChainIndex <= certChainSize && \
                 orderedChainIndex < MAX_CHAINLENGTH );
        }
    ENSURES( iterationCount < FAILSAFE_ITERATIONS_MED );

    /* If there are any certificates left they're not needed for anything 
       so we can free the resources */
    for( i = 0; i < certChainSize && i < MAX_CHAINLENGTH; i++ )
        {
        if( chainInfoValid[ i ] )
            krnlSendNotifier( iCertChain[ i ], IMESSAGE_DECREFCOUNT );
        }
    ENSURES( i < MAX_CHAINLENGTH );

    /* Replace the existing chain with the ordered version */
    memset( iCertChain, 0, sizeof( CRYPT_CERTIFICATE ) * certChainSize );
    if( orderedChainIndex > 0 )
        {
        memcpy( iCertChain, orderedChain,
                sizeof( CRYPT_CERTIFICATE ) * orderedChainIndex );
        }
    *orderedCertChainSize = orderedChainIndex;

    return( CRYPT_OK );
    }

/* Read a collection of certificates in a certificate chain into a 
   certificate object */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2 ) ) \
static int buildCertChain( OUT_HANDLE_OPT CRYPT_CERTIFICATE *iLeafCert, 
                           INOUT_ARRAY( certChainEnd ) CRYPT_CERTIFICATE *iCertChain, 
                           IN_RANGE( 1, MAX_CHAINLENGTH ) const int certChainEnd,
                           IN_KEYID_OPT const CRYPT_KEYID_TYPE keyIDtype,
                           IN_BUFFER_OPT( keyIDlength ) const void *keyID, 
                           IN_LENGTH_KEYID_Z const int keyIDlength )
    {
    CHAIN_INFO chainInfo[ MAX_CHAINLENGTH + 8 ];
    CERT_INFO *certChainPtr;
    CHAINING_INFO chainingInfo;
    int leafNodePos, newCertChainEnd, complianceLevel, status;

    assert( isWritePtr( iLeafCert, sizeof( CRYPT_CERTIFICATE ) ) );
    assert( isWritePtr( iCertChain, \
            sizeof( CRYPT_CERTIFICATE ) * certChainEnd ) );
    assert( ( keyIDtype == CRYPT_KEYID_NONE && \
              keyID == NULL && keyIDlength == 0 ) || \
            ( ( keyIDtype == CRYPT_IKEYID_KEYID || \
                keyIDtype == CRYPT_IKEYID_ISSUERANDSERIALNUMBER ) && \
              isReadPtr( keyID, keyIDlength ) ) );

    REQUIRES( certChainEnd > 0 && certChainEnd <= MAX_CHAINLENGTH );
    REQUIRES( ( keyIDtype == CRYPT_KEYID_NONE && \
                keyID == NULL && keyIDlength == 0 ) || \
              ( ( keyIDtype == CRYPT_IKEYID_KEYID || \
                  keyIDtype == CRYPT_IKEYID_ISSUERANDSERIALNUMBER ) && \
                keyID != NULL && \
                keyIDlength >= MIN_SKID_SIZE && \
                keyIDlength < MAX_ATTRIBUTE_SIZE ) );

    /* Clear return value */
    *iLeafCert = CRYPT_ERROR;

    status = krnlSendMessage( iCertChain[ 0 ], IMESSAGE_GETATTRIBUTE, 
                              &complianceLevel, 
                              CRYPT_OPTION_CERT_COMPLIANCELEVEL );
    if( cryptStatusError( status ) )
        return( status );

    /* We start with a collection of certificates in unknown order (although 
       it's common for the first certificate to be the leaf).  First we 
       extract the chaining information and search the chain for the leaf 
       node */
    status = buildChainInfo( chainInfo, iCertChain, certChainEnd );
    if( cryptStatusError( status ) )
        return( status );
    if( keyID != NULL )
        {
        leafNodePos = findIdentifiedLeafNode( chainInfo, certChainEnd,
                                              keyIDtype, keyID, keyIDlength );
        }
    else
        leafNodePos = findLeafNode( chainInfo, certChainEnd );
    if( cryptStatusError( leafNodePos ) )
        return( leafNodePos );
    ENSURES( leafNodePos >= 0 && leafNodePos < certChainEnd );

    /* We've got the leaf node, remember the leaf certificate */
    *iLeafCert = iCertChain[ leafNodePos ];
    getIssuerChainingInfo( &chainingInfo, &chainInfo[ leafNodePos ] );

    /* Order the remaining certificates up to the root and discard any 
       unneeded certificates */
    status = sortCertChain( iCertChain, &newCertChainEnd, chainInfo, 
                    certChainEnd, leafNodePos, CRYPT_UNUSED, &chainingInfo,
                    ( complianceLevel >= CRYPT_COMPLIANCELEVEL_PKIX_FULL ) ? \
                    TRUE : FALSE );
    if( cryptStatusError( status ) )
        return( status );
    if( newCertChainEnd <= 0 )
        {
        /* There's only one certificate in the chain either due to the 
           chain containing only a single certificate or due to all other 
           certificates being discarded, leave it as a standalone 
           certificate rather than turning it into a chain */
        return( CRYPT_OK );
        }

#ifdef USE_CERTLEVEL_PKIX_FULL
    /* Walk up the chain re-setting the pseudo-selfsigned flag on any
       chain-internal path-kludge certificates if necessary.  This means 
       that if the chain contains n certificates we reset the flag on 
       certificates 0...n-1.  This is required when there's a re-issued 
       certificate kludged into the middle of the path to connect a new CA 
       signing key with a certificate signed with the old key.  Note that 
       this can't detect the case where the first certificate in the chain 
       is a path kludge certificate with further certificates held 
       externally, e.g. in the trusted certificate store, since it appears 
       as a self-signed CA root certificate */
    if( complianceLevel >= CRYPT_COMPLIANCELEVEL_PKIX_FULL )
        {
        int i;

        for( i = 0; i < newCertChainEnd - 1 && i < MAX_CHAINLENGTH; i++ )
            {
            CERT_INFO *certInfoPtr;
            int value;

            /* Check whether this is a self-signed certificate */
            status = krnlSendMessage( iCertChain[ i ], IMESSAGE_GETATTRIBUTE,
                                      &value, CRYPT_CERTINFO_SELFSIGNED );
            if( cryptStatusError( status ) || !value )
                continue;

            /* Convert the self-signed flag into the pseudo self-signed/path
               kludge flag */
            status = krnlAcquireObject( iCertChain[ i ], OBJECT_TYPE_CERTIFICATE, 
                                        ( void ** ) &certInfoPtr, 
                                        CRYPT_ERROR_SIGNALLED );
            if( cryptStatusError( status ) )
                continue;
            certInfoPtr->flags &= ~CERT_FLAG_SELFSIGNED;
            certInfoPtr->flags |= CERT_FLAG_PATHKLUDGE;
            krnlReleaseObject( certInfoPtr->objectHandle );
            }
        ENSURES( i < MAX_CHAINLENGTH );
        }
#endif /* USE_CERTLEVEL_PKIX_FULL */

    /* Finally, we've got the leaf certificate and a chain up to the root.  
       Make the leaf a certificate-chain type and copy in the chain */
    status = krnlAcquireObject( *iLeafCert, OBJECT_TYPE_CERTIFICATE, 
                                ( void ** ) &certChainPtr, 
                                CRYPT_ERROR_SIGNALLED );
    if( cryptStatusError( status ) )
        return( status );
    memcpy( certChainPtr->cCertCert->chain, iCertChain,
            sizeof( CRYPT_CERTIFICATE ) * newCertChainEnd );
    certChainPtr->cCertCert->chainEnd = newCertChainEnd;
    certChainPtr->type = CRYPT_CERTTYPE_CERTCHAIN;
    krnlReleaseObject( certChainPtr->objectHandle );

    return( CRYPT_OK );
    }

/****************************************************************************
*                                                                           *
*                           Copy a Certificate Chain                        *
*                                                                           *
****************************************************************************/

/* Determine whether a certificate is present in a certificate collection 
   based on its fingerprint */

CHECK_RETVAL_BOOL STDC_NONNULL_ARG( ( 1 ) ) \
static BOOLEAN isCertPresent( INOUT_ARRAY( certChainLen ) \
                                    BYTE certChainHashes[][ CRYPT_MAX_HASHSIZE + 8 ],
                              IN_RANGE( 0, MAX_CHAINLENGTH ) const int certChainLen, 
                              IN_HANDLE const CRYPT_CERTIFICATE iCryptCert )
    {
    MESSAGE_DATA msgData;
    int i, status;

    assert( isWritePtr( certChainHashes, \
                        MAX_CHAINLENGTH * CRYPT_MAX_HASHSIZE ) );

    REQUIRES_B( certChainLen >= 0 && certChainLen <= MAX_CHAINLENGTH );
                /* Apparent length may be zero for a chain of size 1 since
                   the leaf certificate has the effective index value -1 */
    REQUIRES_B( isHandleRangeValid( iCryptCert ) );

    /* Get the fingerprint of the (potential) next certificate in the 
       collection.  This leaves it at the end of the existing collection of 
       hashes so that if the certificate is then added to the chain its hash 
       will also be present */
    setMessageData( &msgData, certChainHashes[ certChainLen ], 
                    CRYPT_MAX_HASHSIZE );
    status = krnlSendMessage( iCryptCert, IMESSAGE_GETATTRIBUTE_S,
                              &msgData, CRYPT_CERTINFO_FINGERPRINT );
    if( cryptStatusError( status ) )
        return( status );

    /* Make sure that it isn't already present in the collection */
    for( i = 0; i < certChainLen && i < MAX_CHAINLENGTH; i++ )
        {
        if( !memcmp( certChainHashes[ i ], 
                     certChainHashes[ certChainLen ], msgData.length ) )
            return( TRUE );
        }
    return( FALSE );
    }

/* Copy a certificate chain into a certificate object and canonicalise the 
   chain by ordering the certificates from the leaf certificate up to the 
   root.  This function is used when signing a certificate with a certificate  
   chain and takes as input ( oldCert, oldCert.chain[ ... ] ) and produces 
   as output ( newCert, chain[ oldCert, oldCert.chain[ ... ] ], i.e. the 
   chain for the new certificate contains the old certificate and its 
   attached certificate chain */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
int copyCertChain( INOUT CERT_INFO *certInfoPtr, 
                   IN_HANDLE const CRYPT_HANDLE certChain,
                   const BOOLEAN isCertCollection )
    {
    CRYPT_CERTIFICATE iChainCert;
    CERT_INFO *chainCertInfoPtr;
    CERT_CERT_INFO *destCertChainInfo = certInfoPtr->cCertCert;
    CERT_CERT_INFO *srcCertChainInfo;
    CHAIN_INFO chainInfo[ MAX_CHAINLENGTH + 8 ];
    BYTE certChainHashes[ MAX_CHAINLENGTH + 1 + 8 ][ CRYPT_MAX_HASHSIZE + 8 ];
    const int oldChainEnd = destCertChainInfo->chainEnd;
    int i, status;

    assert( isWritePtr( certInfoPtr, sizeof( CERT_INFO ) ) );

    REQUIRES( isHandleRangeValid( certChain ) );

    status = krnlSendMessage( certChain, IMESSAGE_GETDEPENDENT, &iChainCert, 
                              OBJECT_TYPE_CERTIFICATE );
    if( cryptStatusError( status ) )
        return( status );

    /* If we're building a certificate collection all that we need to ensure 
       is non-duplicate certificates rather than a strict chain.  To handle 
       duplicate checking we build a list of the fingerprints for each 
       certificate in the chain */
    if( isCertCollection )
        {
        for( i = 0; i < destCertChainInfo->chainEnd && i < MAX_CHAINLENGTH; i++ )
            {
            MESSAGE_DATA msgData;

            setMessageData( &msgData, certChainHashes[ i ], 
                            CRYPT_MAX_HASHSIZE );
            status = krnlSendMessage( destCertChainInfo->chain[ i ], 
                                      IMESSAGE_GETATTRIBUTE_S, &msgData, 
                                      CRYPT_CERTINFO_FINGERPRINT );
            if( cryptStatusError( status ) )
                return( status );
            }
        ENSURES( i < MAX_CHAINLENGTH );
        }

    /* Extract the base certificate from the chain and copy it over (the
       isCertPresent() check also sets up the hash for the new certificate 
       in the certChainHashes array) */
    status = krnlAcquireObject( iChainCert, OBJECT_TYPE_CERTIFICATE, 
                                ( void ** ) &chainCertInfoPtr, 
                                CRYPT_ERROR_SIGNALLED );
    if( cryptStatusError( status ) )
        return( status );
    srcCertChainInfo = chainCertInfoPtr->cCertCert;
    if( !isCertCollection || \
        !isCertPresent( certChainHashes, destCertChainInfo->chainEnd, \
                        iChainCert ) )
        {
        if( destCertChainInfo->chainEnd >= MAX_CHAINLENGTH )
            {
            krnlReleaseObject( chainCertInfoPtr->objectHandle );
            return( CRYPT_ERROR_OVERFLOW );
            }
        krnlSendNotifier( iChainCert, IMESSAGE_INCREFCOUNT );
        destCertChainInfo->chain[ destCertChainInfo->chainEnd++ ] = iChainCert;
        }

    /* Copy the rest of the chain.  Because we're about to canonicalise it
       (which re-orders the certificates and deletes unused ones) we copy 
       individual certificates over rather than copying only the base 
       certificate and relying on the chain held in that */
    for( i = 0; i < srcCertChainInfo->chainEnd && i < MAX_CHAINLENGTH; i++ )
        {
        const CRYPT_CERTIFICATE iCopyCert = srcCertChainInfo->chain[ i ];

        /* If it's an (unordered) certificate collection, make sure that 
           there are no duplicates */
        if( isCertCollection && \
            isCertPresent( certChainHashes, destCertChainInfo->chainEnd,
                            srcCertChainInfo->chain[ i ] ) )
            continue;

        /* Copy the next certificate from the source to the destination */
        if( destCertChainInfo->chainEnd >= MAX_CHAINLENGTH )
            {
            status = CRYPT_ERROR_OVERFLOW;
            break;
            }
        krnlSendNotifier( iCopyCert, IMESSAGE_INCREFCOUNT );
        destCertChainInfo->chain[ destCertChainInfo->chainEnd++ ] = iCopyCert;
        }
    ENSURES( i < MAX_CHAINLENGTH );
    srcCertChainInfo = NULL;    /* Make the release explicit */
    krnlReleaseObject( chainCertInfoPtr->objectHandle );
    if( cryptStatusError( status ) )
        {
        /* An error at this point indicates that the upper limit on chain
           length isn't sufficient so we throw a (debug) exception if we 
           get here */
        DEBUG_DIAG(( "Maximum chain length %d exceeded", MAX_CHAINLENGTH ));
        assert( DEBUG_WARN );

        /* Clean up the newly-copied certificates if necessary */
        if( destCertChainInfo->chainEnd > oldChainEnd )
            {
            freeCertChain( &destCertChainInfo->chain[ oldChainEnd ],
                           destCertChainInfo->chainEnd - oldChainEnd );
            }

        return( status );
        }

    /* If we're building an unordered certificate collection, mark the 
       certificate chain object as a certificate collection only and exit.  
       This is a pure container object for which only the certificate chain 
       member contains certificates, the base certificate object doesn't 
       correspond to an actual certificate */
    if( isCertCollection )
        {
        certInfoPtr->flags |= CERT_FLAG_CERTCOLLECTION;
        return( CRYPT_OK );
        }

    /* If the chain being attached consists of a single certificate (which 
       occurs when we're building a new chain by signing a certificate with 
       a CA certificate) we don't have to bother doing anything else */
    if( oldChainEnd <= 0 )
        return( CRYPT_OK );

    /* Extract the chaining information from each certificate and use it to 
       sort the chain.  Since we know what the leaf certificate is and since 
       chaining information such as the encoded DN data in the certinfo 
       structure may not have been set up yet if it contains an unsigned 
       certificate we feed in the leaf certificate and omit the chaining 
       information */
    status = buildChainInfo( chainInfo, destCertChainInfo->chain,
                             destCertChainInfo->chainEnd );
    if( cryptStatusError( status ) )
        {
        /* Clean up the newly-copied certificates if necessary */
        if( destCertChainInfo->chainEnd > oldChainEnd )
            {
            freeCertChain( &destCertChainInfo->chain[ oldChainEnd ],
                           destCertChainInfo->chainEnd - oldChainEnd );
            }

        return( status );
        }
    return( sortCertChain( destCertChainInfo->chain, &destCertChainInfo->chainEnd, 
                           chainInfo, destCertChainInfo->chainEnd, CRYPT_UNUSED,
                           iChainCert, NULL, FALSE ) );
    }

/****************************************************************************
*                                                                           *
*                       Read Certificate-bagging Records                    *
*                                                                           *
****************************************************************************/

/* Read the PKCS #7/CMS wrapper for a certificate chain */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
static int readCertChainWrapper( INOUT STREAM *stream )
    {
    BYTE oid[ MAX_OID_SIZE + 8 ];
    long integer;
    int length, oidLength, status;

    assert( isWritePtr( stream, sizeof( STREAM ) ) );

    /* Skip the contentType OID, read the content encapsulation and header 
       if necessary, and burrow down into the PKCS #7/CMS content.  We use 
       readEncodedOID() when reading the wrapper rather than readUniversal() 
       to make sure that we're at least getting an OID at this point */
    status = readEncodedOID( stream, oid, MAX_OID_SIZE, &oidLength, 
                             BER_OBJECT_IDENTIFIER );
    if( cryptStatusError( status ) )
        return( status );
    readConstructed( stream, NULL, 0 );
    readSequence( stream, NULL );

    /* Read the version number (1 = PKCS #7 v1.5, 2 = PKCS #7 v1.6 (never 
       proceeded beyond the draft stage), 3 = S/MIME with attribute 
       certificate(s)), and (should be empty) SET OF 
       DigestAlgorithmIdentifier */
    readShortInteger( stream, &integer );
    status = readSet( stream, &length );
    if( cryptStatusError( status ) )
        return( status );
    if( integer < 1 || integer > 3 )
        return( CRYPT_ERROR_BADDATA );
    if( length > 0 )
        sSkip( stream, length );

    /* Read the ContentInfo header, contentType OID (ignored) and the inner 
       content encapsulation.  We again use readEncodedOID() rather than 
       readUniversal() to make sure that we're at least getting an OID at 
       this point.

       Sometimes we may (incorrectly) get passed actual signed data rather 
       than degenerate zero-length data signifying a pure certificate chain, 
       if there's data present then we skip it */
    readSequenceI( stream, &length );
    status = readEncodedOID( stream, oid, MAX_OID_SIZE, &oidLength, 
                             BER_OBJECT_IDENTIFIER );
    if( cryptStatusError( status ) )
        return( status );
    if( length != CRYPT_UNUSED )
        {
        /* We've got definite-length data, see if there's any content 
           present alongside the contentType OID.  If it's a correctly-
           formatted certificate chain (i.e. the content is zero-length) 
           we're done */
        length -= oidLength;
        if( length < 0 || length > MAX_INTLENGTH )
            return( CRYPT_ERROR_BADDATA );
        if( length == 0 )
            return( CRYPT_OK );
        
        /* The ContentInfo has the content field present, it may be signed
           data (with attached certificates) being passed in for use as a
           certificate chain, skip the content to get to the chain */
        return( readUniversal( stream ) );
        }

    /* It's an indefinite-length ContentInfo, check for the EOC.  If there's 
       no EOC present that means that there's indefinite-length inner data 
       present and we have to dig down further */
    status = checkEOC( stream );
    if( cryptStatusError( status ) )
        return( status );
    if( status == FALSE )
        {
        int innerLength;

        /* Try and get the length from the ContentInfo.  We're really 
           reaching the point of diminishing returns here, if we can't get a 
           length at this point we bail out since we're not even supposed to 
           be getting down to this level */
        status = readConstructedI( stream, &innerLength, 0 );
        if( cryptStatusError( status ) )
            return( status );
        if( innerLength == CRYPT_UNUSED )
            return( CRYPT_ERROR_BADDATA );
        return( sSkip( stream, innerLength ) );
        }

    return( CRYPT_OK );
    }

/* Read a single certificate in a chain */

CHECK_RETVAL_SPECIAL STDC_NONNULL_ARG( ( 1, 2 ) ) \
static int readSingleCert( INOUT STREAM *stream, 
                           OUT_HANDLE_OPT CRYPT_CERTIFICATE *iCryptCert,
                           IN_HANDLE const CRYPT_USER iCryptOwner,
                           IN_ENUM( CRYPT_CERTTYPE ) const CRYPT_CERTTYPE_TYPE type,
                           const BOOLEAN dataOnlyCert,
                           const BOOLEAN isIndefiniteLength )
    {
    int length, status;

    assert( isWritePtr( stream, sizeof( STREAM ) ) );
    assert( isWritePtr( iCryptCert, sizeof( CRYPT_CERTIFICATE ) ) );

    REQUIRES( iCryptOwner == DEFAULTUSER_OBJECT_HANDLE || \
              isHandleRangeValid( iCryptOwner ) );
    REQUIRES( type == CRYPT_CERTTYPE_CERTCHAIN || \
              type == CRYPT_ICERTTYPE_CMS_CERTSET || \
              type == CRYPT_ICERTTYPE_SSL_CERTCHAIN );

    /* Clear return value */
    *iCryptCert = CRYPT_ERROR;

    /* If it's an SSL certificate chain then there's a 24-bit length field 
       between certificates */
    if( type == CRYPT_ICERTTYPE_SSL_CERTCHAIN )
        {
        status = sSkip( stream, 3 );
        if( cryptStatusError( status ) )
            return( status );
        }

    /* Find out how large the certificate data is */
    status = getStreamObjectLength( stream, &length );
    if( cryptStatusError( status ) )
        return( status );

    /* Since SSL certificate chains contain certificates interspersed with 
       non-certificate SSL length data the higher-level code can't check the 
       encoding, so we have to perform the check here.  Technically this 
       isn't really necessary since importCertFromStream() imports the 
       certificate via a kernel message which means that the encoding is 
       checked anyway, but this is an implementation-specific detail that we 
       can't assume will hold for future versions so we make the check 
       explicit here */
    if( type == CRYPT_ICERTTYPE_SSL_CERTCHAIN )
        {
        void *certDataPtr;
        int complianceLevel;

        status = krnlSendMessage( iCryptOwner, IMESSAGE_GETATTRIBUTE,
                                  &complianceLevel,
                                  CRYPT_OPTION_CERT_COMPLIANCELEVEL );
        if( cryptStatusError( status ) )
            return( status );
        if( complianceLevel > CRYPT_COMPLIANCELEVEL_OBLIVIOUS )
            {
            status = sMemGetDataBlock( stream, &certDataPtr, length );
            if( cryptStatusOK( status ) && \
                cryptStatusError( \
                    checkObjectEncoding( certDataPtr, length ) ) )
                status = CRYPT_ERROR_BADDATA;
            }
        if( cryptStatusError( status ) )
            return( status );
        }

    /* Read the next certificate and add it to the chain.  When importing 
       the chain from an external (untrusted) source we create standard 
       certificates so that we can check the signatures on each link in the 
       chain.  When importing from a trusted source we create data-only 
       certificates, once we've got all of the certificates and know which 
       certificate is the leaf we can go back and decode the public key 
       information for it */
    status = importCertFromStream( stream, iCryptCert, iCryptOwner,
                                   dataOnlyCert ? \
                                        CRYPT_ICERTTYPE_DATAONLY : \
                                        CRYPT_CERTTYPE_CERTIFICATE, length );
    if( cryptStatusError( status ) )
        return( status );

    /* If the certificate chain is encoded using the indefinite form and we 
       find the EOC octets following the certificate that we've just read, 
       tell the caller */
    if( isIndefiniteLength )
        {
        status = checkEOC( stream );
        if( cryptStatusError( status ) )
            {
            krnlSendNotifier( *iCryptCert, IMESSAGE_DECREFCOUNT );
            *iCryptCert = CRYPT_ERROR;
            return( status );
            }
        if( status == TRUE )
            {
            /* We've seen EOC octets, tell the caller that we're done */
            return( OK_SPECIAL );
            }
        }

    return( CRYPT_OK );
    }

/* Read certificate chain/sequence information */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2 ) ) \
int readCertChain( INOUT STREAM *stream, 
                   OUT_HANDLE_OPT CRYPT_CERTIFICATE *iCryptCert,
                   IN_HANDLE const CRYPT_USER iCryptOwner,
                   IN_ENUM( CRYPT_CERTTYPE ) const CRYPT_CERTTYPE_TYPE type,
                   IN_KEYID_OPT const CRYPT_KEYID_TYPE keyIDtype,
                   IN_BUFFER_OPT( keyIDlength ) const void *keyID, 
                   IN_LENGTH_KEYID_Z const int keyIDlength,
                   const BOOLEAN dataOnlyCert )
    {
    CRYPT_CERTIFICATE iCertChain[ MAX_CHAINLENGTH + 8 ];
    int certSequenceLength = DUMMY_INIT, endPos = 0, certChainEnd = 0;
    int iterationCount, status;

    assert( isWritePtr( stream, sizeof( STREAM ) ) );
    assert( isWritePtr( iCryptCert, sizeof( CRYPT_CERTIFICATE ) ) );
    assert( ( keyIDtype == CRYPT_KEYID_NONE && keyID == NULL && \
              keyIDlength == 0 ) || \
            ( ( keyIDtype == CRYPT_IKEYID_KEYID || \
                keyIDtype == CRYPT_IKEYID_ISSUERANDSERIALNUMBER ) && \
              isReadPtr( keyID, keyIDlength ) && \
              keyIDlength >= MIN_SKID_SIZE ) );

    REQUIRES( iCryptOwner == DEFAULTUSER_OBJECT_HANDLE || \
              isHandleRangeValid( iCryptOwner ) );
    REQUIRES( type == CRYPT_CERTTYPE_CERTCHAIN || \
              type == CRYPT_ICERTTYPE_CMS_CERTSET || \
              type == CRYPT_ICERTTYPE_SSL_CERTCHAIN );
    REQUIRES( ( keyIDtype == CRYPT_KEYID_NONE && \
                keyID == NULL && keyIDlength == 0 ) || \
              ( ( keyIDtype == CRYPT_IKEYID_KEYID || \
                  keyIDtype == CRYPT_IKEYID_ISSUERANDSERIALNUMBER ) && \
                keyID != NULL && \
                keyIDlength >= MIN_SKID_SIZE && \
                keyIDlength < MAX_ATTRIBUTE_SIZE ) );

    /* Clear return value */
    *iCryptCert = CRYPT_ERROR;

    switch( type )
        {
        case CRYPT_CERTTYPE_CERTCHAIN:
            status = readCertChainWrapper( stream );
            if( cryptStatusError( status ) )
                break;
            /* Fall through */

        case CRYPT_ICERTTYPE_CMS_CERTSET:
            status = readConstructedI( stream, &certSequenceLength, 0 );
            break;

        case CRYPT_ICERTTYPE_SSL_CERTCHAIN:
            /* There's no outer wrapper to give us length information for an 
               SSL certificate chain, however the length will be equal to the 
               total remaining stream size */
            certSequenceLength = sMemDataLeft( stream );
            status = CRYPT_OK;
            break;

        default:
            retIntError();
        }
    if( cryptStatusError( status ) )
        return( status );

    /* If it's a definite-length chain, determine where it ends */
    if( certSequenceLength != CRYPT_UNUSED )
        endPos = stell( stream ) + certSequenceLength;

    /* We've reached the certificate(s), read the collection of certificates 
       into certificate objects.  We allow for a bit of slop for software 
       that gets the length encoding wrong by a few bytes.  Note that the 
       limit is given as FAILSAFE_ITERATIONS_MED since we're using it as a 
       fallback check on the existing MAX_CHAINLENGTH check.  In other words 
       anything over MAX_CHAINLENGTH is handled as a normal error and it's 
       only if we exceed this that we have an internal error */
    for( iterationCount = 0;
         ( certSequenceLength == CRYPT_UNUSED || \
           stell( stream ) <= endPos - MIN_ATTRIBUTE_SIZE ) && \
            iterationCount < FAILSAFE_ITERATIONS_MED; 
         iterationCount++ )
        {
        CRYPT_CERTIFICATE iNewCert = DUMMY_INIT;

        /* Make sure that we don't overflow the chain */
        if( certChainEnd >= MAX_CHAINLENGTH )
            {
            freeCertChain( iCertChain, certChainEnd );
            return( CRYPT_ERROR_OVERFLOW );
            }

        /* Read the next certificate in the chain */
        status = readSingleCert( stream, &iNewCert, iCryptOwner, type, 
                                 dataOnlyCert,
                                 ( certSequenceLength == CRYPT_UNUSED ) ? \
                                    TRUE : FALSE );
        if( cryptStatusError( status ) && status != OK_SPECIAL )
            {
            if( certChainEnd > 0 )
                freeCertChain( iCertChain, certChainEnd );
            return( status );
            }
        iCertChain[ certChainEnd++ ] = iNewCert;
        if( status == OK_SPECIAL )
            break;  /* We've reached the end of the chain */
        }
    ENSURES( iterationCount < FAILSAFE_ITERATIONS_MED );

    /* We must have read at least one certificate in order to create a 
       chain */
    if( certChainEnd <= 0 )
        return( CRYPT_ERROR_BADDATA );

    /* Build the complete chain from the individual certificates */
    status = buildCertChain( iCryptCert, iCertChain, certChainEnd, 
                             keyIDtype, keyID, keyIDlength );
    if( cryptStatusError( status ) )
        {
        freeCertChain( iCertChain, certChainEnd );
        return( status );
        }

    return( CRYPT_OK );
    }

/* Fetch a sequence of certificates from an object to create a certificate 
   chain */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 4 ) ) \
int assembleCertChain( OUT CRYPT_CERTIFICATE *iCertificate,
                       IN_HANDLE const CRYPT_HANDLE iCertSource,
                       IN_KEYID const CRYPT_KEYID_TYPE keyIDtype,
                       IN_BUFFER( keyIDlength ) const void *keyID, 
                       IN_LENGTH_KEYID const int keyIDlength,
                       IN_FLAGS( KEYMGMT ) const int options )
    {
    CRYPT_CERTIFICATE iCertChain[ MAX_CHAINLENGTH + 8 ], lastCert;
    MESSAGE_KEYMGMT_INFO getnextcertInfo;
    const int chainOptions = options & KEYMGMT_FLAG_DATAONLY_CERT;
    int stateInfo = CRYPT_ERROR, certChainEnd = 1;
    int iterationCount, status;

    assert( isWritePtr( iCertificate, sizeof( CRYPT_CERTIFICATE ) ) );
    assert( isReadPtr( keyID, keyIDlength ) && \
            keyIDlength >= MIN_NAME_LENGTH && \
            keyIDlength < MAX_ATTRIBUTE_SIZE );

    REQUIRES( isHandleRangeValid( iCertSource ) );
    REQUIRES( keyIDtype > CRYPT_KEYID_NONE && \
              keyIDtype < CRYPT_KEYID_LAST );
    REQUIRES( keyIDlength >= MIN_NAME_LENGTH && \
              keyIDlength < MAX_ATTRIBUTE_SIZE );
    REQUIRES( options >= KEYMGMT_FLAG_NONE && options < KEYMGMT_FLAG_MAX && \
              ( options & ~KEYMGMT_MASK_CERTOPTIONS ) == 0 );

    /* Get the initial certificate based on the key ID */
    setMessageKeymgmtInfo( &getnextcertInfo, keyIDtype, keyID, keyIDlength, 
                           &stateInfo, sizeof( int ), 
                           options & KEYMGMT_MASK_CERTOPTIONS );
    status = krnlSendMessage( iCertSource, IMESSAGE_KEY_GETFIRSTCERT,
                              &getnextcertInfo, KEYMGMT_ITEM_PUBLICKEY );
    if( cryptStatusError( status ) )
        return( status );
    iCertChain[ 0 ] = lastCert = getnextcertInfo.cryptHandle;

    /* Fetch subsequent certificates that make up the chain based on the 
       state information.  Since the basic options apply only to the leaf 
       certificate we only allow the data-only certificate flag at this 
       point.  See the comment in readCertChain() for the use of 
       FAILSAFE_ITERATIONS_MED for the bounds check */
    setMessageKeymgmtInfo( &getnextcertInfo, CRYPT_KEYID_NONE, NULL, 0, 
                           &stateInfo, sizeof( int ), chainOptions );
    for( iterationCount = 0;
         cryptStatusOK( status ) && \
            iterationCount < FAILSAFE_ITERATIONS_MED; 
         iterationCount++ )
        {
        int selfSigned;

        /* If we've reached a self-signed (CA root) certificate, stop.  Note 
           that this can't detect PKIX path-kludge certificates which look 
           identical to CA root certificates and can only be reliably 
           identified if they're present in the middle of a pre-built 
           chain */
        status = krnlSendMessage( lastCert, IMESSAGE_GETATTRIBUTE, 
                                  &selfSigned, CRYPT_CERTINFO_SELFSIGNED );
        if( cryptStatusError( status ) || selfSigned > 0 )
            break;

        /* Get the next certificate in the chain from the source, import it,
           and add it to the collection */
        getnextcertInfo.cryptHandle = CRYPT_ERROR;  /* Reset result handle */
        status = krnlSendMessage( iCertSource, IMESSAGE_KEY_GETNEXTCERT,
                                  &getnextcertInfo, KEYMGMT_ITEM_PUBLICKEY );
        if( cryptStatusError( status ) )
            {
            /* If we get a notfound error this is OK since it just means 
               that we've reached the end of the chain */
            if( status == CRYPT_ERROR_NOTFOUND )
                status = CRYPT_OK;

            break;
            }

        /* Make sure that we don't overflow the chain */
        if( certChainEnd >= MAX_CHAINLENGTH )
            {
            krnlSendNotifier( getnextcertInfo.cryptHandle,
                              IMESSAGE_DECREFCOUNT );
            status = CRYPT_ERROR_OVERFLOW;
            break;
            }

        iCertChain[ certChainEnd++ ] = lastCert = getnextcertInfo.cryptHandle;
        }
    ENSURES( iterationCount < FAILSAFE_ITERATIONS_MED );
    if( cryptStatusError( status ) )
        {
        freeCertChain( iCertChain, certChainEnd );
        return( status );
        }

    /* Build the complete chain from the individual certificates */
    status = buildCertChain( iCertificate, iCertChain, certChainEnd, 
                             CRYPT_KEYID_NONE, NULL, 0 );
    if( cryptStatusError( status ) )
        {
        freeCertChain( iCertChain, certChainEnd );
        return( status );
        }

    return( CRYPT_OK );
    }

/****************************************************************************
*                                                                           *
*                       Write Certificate-bagging Records                   *
*                                                                           *
****************************************************************************/

/* Determine the size of and write a certificate path from a base 
   certificate up to the root.  This gets a bit complicated because 
   alongside the overall length, SSL requires that we return component-by-
   component lengths that need to be inserted as 24-bit (3 byte) values 
   between each certificate.  To handle this we take as an optional 
   parameter an array used to store the individual path component lengths */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2 ) ) \
static int sizeofCertPath( const CERT_INFO *certInfoPtr,
                           OUT_LENGTH_SHORT_Z int *certPathLength,
                           OUT_ARRAY_OPT_C( MAX_CHAINLENGTH ) int *certSizeInfo )
    {
    CERT_CERT_INFO *certChainInfo = certInfoPtr->cCertCert;
    int length = 0, i;

    assert( isReadPtr( certInfoPtr, sizeof( CERT_INFO ) ) );
    assert( isWritePtr( certPathLength, sizeof( int ) ) );
    assert( certSizeInfo == NULL || \
            isWritePtr( certSizeInfo, sizeof( int ) * MAX_CHAINLENGTH ) );

    /* Clear return values */
    *certPathLength = 0;
    if( certSizeInfo != NULL )
        memset( certSizeInfo, 0, sizeof( int ) * MAX_CHAINLENGTH );

    /* Evaluate the size of the current certificate and the issuer 
       certificates in the chain.  If it's a certificate collection it's 
       just a container for random certificates but not a certificate in its 
       own right so we skip the leaf certificate */
    if( !( certInfoPtr->flags & CERT_FLAG_CERTCOLLECTION ) )
        {
        length = certInfoPtr->certificateSize;
        if( certSizeInfo != NULL )
            length += 3;
        }
    for( i = 0; i < certChainInfo->chainEnd && i < MAX_CHAINLENGTH; i++ )
        {
        MESSAGE_DATA msgData;
        int status;

        setMessageData( &msgData, NULL, 0 );
        status = krnlSendMessage( certChainInfo->chain[ i ], 
                                  IMESSAGE_CRT_EXPORT, &msgData, 
                                  CRYPT_CERTFORMAT_CERTIFICATE );
        if( cryptStatusError( status ) )
            return( status );
        length += msgData.length;
        if( certSizeInfo != NULL )
            {
            certSizeInfo[ i ] = msgData.length;
            length += 3;
            }
        }
    ENSURES( i < MAX_CHAINLENGTH );
    *certPathLength = length;

    return( CRYPT_OK );
    }

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2 ) ) \
static int writeCertPath( INOUT STREAM *stream, 
                          const CERT_INFO *certInfoPtr,
                          IN_ARRAY_OPT_C( MAX_CHAINLENGTH ) \
                                const int *certSizeInfo )

    {
    CERT_CERT_INFO *certChainInfo = certInfoPtr->cCertCert;
    int i, status = CRYPT_OK;

    assert( isWritePtr( stream, sizeof( STREAM ) ) );
    assert( isReadPtr( certInfoPtr, sizeof( CERT_INFO ) ) );
    assert( certSizeInfo == NULL || \
            isReadPtr( certSizeInfo, sizeof( int ) * MAX_CHAINLENGTH ) );

    /* Write the current certificate and the associated certificate chain up 
       to the root.  If it's a certificate collection it's just a container 
       for random certificates but not a certificate in its own right so we 
       skip the leaf certificate */
    if( !( certInfoPtr->flags & CERT_FLAG_CERTCOLLECTION ) )
        {
        if( certSizeInfo != NULL )
            {
            sputc( stream, 0 );
            writeUint16( stream, certInfoPtr->certificateSize );
            }
        status = swrite( stream, certInfoPtr->certificate, 
                         certInfoPtr->certificateSize );
        }
    for( i = 0; cryptStatusOK( status ) && \
                i < certChainInfo->chainEnd && \
                i < MAX_CHAINLENGTH; i++ )
        {
        if( certSizeInfo != NULL )
            {
            sputc( stream, 0 );
            writeUint16( stream, certSizeInfo[ i ] );
            }
        status = exportCertToStream( stream, certChainInfo->chain[ i ], 
                                     CRYPT_CERTFORMAT_CERTIFICATE );
        }
    ENSURES( i < MAX_CHAINLENGTH );

    return( status );
    }

/* Write certificate chain/sequence information:

    CertChain ::= SEQUENCE {
        contentType             OBJECT IDENTIFIER,  -- signedData
        content           [ 0 ] EXPLICIT SEQUENCE {
            version             INTEGER (1),
            digestAlgorithms    SET OF AlgorithmIdentifier, -- SIZE(0)
            contentInfo         SEQUENCE {
                signedData      OBJECT IDENTIFIER   -- data
                }
            certificates  [ 0 ] SET OF {
                                    Certificate
                }
            }
        signerInfos             SET OF SignerInfo           -- SIZE(0)
        } */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
int sizeofCertCollection( const CERT_INFO *certInfoPtr,
                          IN_ENUM( CRYPT_CERTFORMAT ) \
                            const CRYPT_CERTFORMAT_TYPE certFormatType )
    {
    int length, status;

    assert( isReadPtr( certInfoPtr, sizeof( CERT_INFO ) ) );

    REQUIRES( certFormatType == CRYPT_ICERTFORMAT_CERTSET || \
              certFormatType == CRYPT_ICERTFORMAT_CERTSEQUENCE || \
              certFormatType == CRYPT_ICERTFORMAT_SSL_CERTCHAIN );

    /* If it's an SSL certificate chain then we have to pass in a dummy
       component-length pointer to ensure that it's evaluated as an SSL 
       chain with intermediate lengths rather than a straight PKCS #7/CMS
       chain */
    if( certFormatType == CRYPT_ICERTFORMAT_SSL_CERTCHAIN )
        {
        int certSizeInfo[ MAX_CHAINLENGTH + 8 ];

        status = sizeofCertPath( certInfoPtr, &length, certSizeInfo );
        }
    else
        {
        /* It's a standard PKCS #7/CMS chain */
        status = sizeofCertPath( certInfoPtr, &length, NULL );
        if( cryptStatusError( status ) )
            return( status );
        status = length = sizeofObject( length );
        }
    if( cryptStatusError( status ) )
        return( status );
    return( length );
    }

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2 ) ) \
int writeCertCollection( INOUT STREAM *stream, 
                         const CERT_INFO *certInfoPtr,
                         IN_ENUM( CRYPT_CERTFORMAT ) \
                            const CRYPT_CERTFORMAT_TYPE certFormatType )
    {
    int certSizeInfo[ MAX_CHAINLENGTH + 8 ];
    int *certSizePtr = \
            ( certFormatType == CRYPT_ICERTFORMAT_SSL_CERTCHAIN ) ? \
            certSizeInfo : NULL;
    int certCollectionLength, status;

    assert( isWritePtr( stream, sizeof( STREAM ) ) );
    assert( isReadPtr( certInfoPtr, sizeof( CERT_INFO ) ) );
    
    REQUIRES( certFormatType == CRYPT_ICERTFORMAT_CERTSET || \
              certFormatType == CRYPT_ICERTFORMAT_CERTSEQUENCE || \
              certFormatType == CRYPT_ICERTFORMAT_SSL_CERTCHAIN );

    status = sizeofCertPath( certInfoPtr, &certCollectionLength, 
                             certSizePtr );
    if( cryptStatusError( status ) )
        return( status );
    switch( certFormatType )
        {
        case CRYPT_ICERTFORMAT_CERTSET:
            writeConstructed( stream, certCollectionLength, 0 );
            break;

        case CRYPT_ICERTFORMAT_CERTSEQUENCE:
            writeSequence( stream, certCollectionLength );
            break;

        case CRYPT_ICERTFORMAT_SSL_CERTCHAIN:
            break;

        default:
            retIntError();
        }
    return( writeCertPath( stream, certInfoPtr, certSizePtr ) );
    }

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2 ) ) \
int writeCertChain( INOUT STREAM *stream, 
                    const CERT_INFO *certInfoPtr )
    {
    int certSetLength, innerLength, status;

    assert( isWritePtr( stream, sizeof( STREAM ) ) );
    assert( isReadPtr( certInfoPtr, sizeof( CERT_INFO ) ) );

    status = sizeofCertPath( certInfoPtr, &certSetLength, NULL );
    if( cryptStatusError( status ) )
        return( status );

    /* Determine how big the encoded certificate chain/sequence will be */
    innerLength = sizeofShortInteger( 1 ) + ( int ) sizeofObject( 0 ) + \
                      ( int ) sizeofObject( sizeofOID( OID_CMS_DATA ) ) + \
                      ( int ) sizeofObject( certSetLength ) + \
                      ( int ) sizeofObject( 0 );

    /* Write the outer SEQUENCE wrapper, contentType, and content wrapper */
    writeSequence( stream, 
                   sizeofOID( OID_CMS_SIGNEDDATA ) + \
                    ( int ) sizeofObject( sizeofObject( innerLength ) ) );
    swrite( stream, OID_CMS_SIGNEDDATA, sizeofOID( OID_CMS_SIGNEDDATA ) );
    writeConstructed( stream, sizeofObject( innerLength ), 0 );
    writeSequence( stream, innerLength );

    /* Write the inner content */
    writeShortInteger( stream, 1, DEFAULT_TAG );
    writeSet( stream, 0 );
    writeSequence( stream, sizeofOID( OID_CMS_DATA ) );
    swrite( stream, OID_CMS_DATA, sizeofOID( OID_CMS_DATA ) );
    writeConstructed( stream, certSetLength, 0 );
    status = writeCertPath( stream, certInfoPtr, NULL );
    if( cryptStatusOK( status ) )
        status = writeSet( stream, 0 );
    return( status );
    }
#endif /* USE_CERTIFICATES */