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

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

/* Assemble a single certificate chain from a collection of certificates,
   consisting of the components in the chain.  This code implements the 
   principle of least surprise and explicitly constructs a single 
   unambiguous chain rather than trying to handle the spaghetti PKI mess,
   for the specific reason that non-web use can't tolerate surprises where 
   some other path through the spaghetti suddenly trusts a certificate that 
   no-one is expecting to be trusted.  In particular with the web PKI the
   endless churn of cross-certification and de-certification means that 
   things can pop in and out of trust more or less at random, while we want
   to build a chain that the caller is expecting to be trusted, not that's
   inadvertently trusted via some cross-certification that they've never 
   heard of before */

/* 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.  We don't bother making these safe pointers because they've 
   live only as long as standard stack-based pointers */

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 */
	DATAPTR attributes;
	} 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 >= MIN_DN_SIZE && \
		  ( 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 ) )

/* Match an identifier in a chaining-information structure */

#define matchSubjectKeyID( chainInfo, keyID, keyIDlength ) \
		( ( chainInfo )->subjectKeyIDsize > MIN_SKID_SIZE && \
		  ( chainInfo )->subjectKeyIDsize == ( keyIDlength ) && \
		  !memcmp( ( chainInfo )->subjectKeyIdentifier, \
				   keyID, keyIDlength ) )

#define matchIssuerDN( chainInfo, issuerDNptr, issuerDNsize ) \
		( ( chainInfo )->issuerDNsize >= MIN_DN_SIZE && \
		  (	chainInfo )->issuerDNsize == ( issuerDNsize ) && \
			!memcmp( ( chainInfo)->issuerDN, issuerDNptr, \
					 issuerDNsize ) )

#ifdef USE_CERTIFICATES

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

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

STDC_NONNULL_ARG( ( 1, 2 ) ) \
static void getSubjectChainingInfo( OUT_PTR 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_PTR 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/TLS 
   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( IN_PTR const CHAINING_INFO *chainingInfo,
						  IN_PTR const CHAIN_INFO *chainInfo,
						  IN_BOOL const BOOLEAN useStrictChaining )
	{
	BOOLEAN dnChains = FALSE, keyIDchains = FALSE;

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

	REQUIRES_B( isBooleanValue( useStrictChaining ) );

	/* 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 then 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_PTR CERT_INFO *certInfoPtr,
								 IN_ATTRIBUTE \
									const CRYPT_ATTRIBUTE_TYPE attributeType,
								 OUT_BUFFER_ALLOC_OPT( *attributeLength ) \
									const void **attributePtrPtr, 
								 OUT_DATALENGTH_Z int *attributeLength )
	{
	DATAPTR_ATTRIBUTE 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( DATAPTR_ISNULL( attributePtr ) )
		{
		/* If the chaining attribute data isn't present then 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 )
	{
	LOOP_INDEX i;

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

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

	LOOP_EXT( i = 0, i < certChainSize, i++, MAX_CHAINLENGTH )
		{
		ENSURES_V( LOOP_INVARIANT_EXT( i, 0, certChainSize - 1,
									   MAX_CHAINLENGTH ) );

		/* If we ran into an error while working with a certificate in the 
		   chain then this position may be empty, in which case we skip it */
		if( iCertChain[ i ] == CRYPT_ERROR )
			continue;

		REQUIRES_V( isHandleRangeValid( iCertChain[ i ] ) );

		/* Clear the certificate at this position */
		krnlSendNotifier( iCertChain[ i ], IMESSAGE_DESTROY );
		iCertChain[ i ] = CRYPT_ERROR;
		}
	ENSURES_V( LOOP_BOUND_OK );
	}

/* Convert a certificate object into a certificate-chain object.  This is 
   necessary because at the point when we're importing the certificates
   to build the chain we don't know which one is the leaf so we have to
   import them all as certificates, and once that's done we can't change
   the object type any more.  Because of this the only way to change
   the object type is to re-create it as a certificate-chain object */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
static int convertCertToChain( OUT_HANDLE_OPT CRYPT_CERTIFICATE *iCertChain,
							   IN_HANDLE CRYPT_CERTIFICATE iCertificate,
							   IN_BOOL const BOOLEAN isDataOnlyCert )
	{
	MESSAGE_CREATEOBJECT_INFO createInfo;
	ERROR_INFO localErrorInfo;
	DYNBUF certDB;
	int status;

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

	REQUIRES( isHandleRangeValid( iCertificate ) );
	REQUIRES( isBooleanValue( isDataOnlyCert ) );

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

	/* Export the leaf certificate and re-import it to create the required 
	   certificate-chain object, specifying KEYMGMT_FLAG_CERT_AS_CERTCHAIN 
	   to ensure that the certificate is imported as a single-entry
	   certificate chain.  Since this is just a straight export-reimport
	   we don't do anything with the error information since it's both 
	   unlikely to occur and unlikely to prove useful */
	clearErrorInfo( &localErrorInfo );
	status = dynCreateCert( &certDB, iCertificate, 
							CRYPT_CERTFORMAT_CERTIFICATE );
	if( cryptStatusError( status ) )
		return( status );
	setMessageCreateObjectIndirectInfoEx( &createInfo, 
							dynData( certDB ), dynLength( certDB ), 
							CRYPT_CERTTYPE_CERTIFICATE, isDataOnlyCert ? \
								KEYMGMT_FLAG_DATAONLY_CERT | \
								KEYMGMT_FLAG_CERT_AS_CERTCHAIN : \
								KEYMGMT_FLAG_CERT_AS_CERTCHAIN,
							&localErrorInfo );
	status = krnlSendMessage( SYSTEM_OBJECT_HANDLE,
							  IMESSAGE_DEV_CREATEOBJECT_INDIRECT,
							  &createInfo, OBJECT_TYPE_CERTIFICATE );
	dynDestroy( &certDB );
	if( cryptStatusError( status ) )
		return( status );

	/* We've now got the same certificate object as before but with a 
	   subtype of 'certificate chain' rather than 'certificate', replace the 
	   existing object with the new one */
	krnlSendNotifier( iCertificate, IMESSAGE_DESTROY );
	*iCertChain = createInfo.cryptHandle;

	return( CRYPT_OK );
	}

/****************************************************************************
*																			*
*							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 )
	{
	LOOP_INDEX i;

	assert( isWritePtrDynamic( chainInfo, \
							   sizeof( CHAIN_INFO ) * certChainSize ) );
	assert( isReadPtrDynamic( 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 */
	LOOP_EXT( i = 0, i < certChainSize, i++, MAX_CHAINLENGTH )
		{
		CERT_INFO *certChainPtr;
		int status;

		ENSURES( LOOP_INVARIANT_EXT( i, 0, certChainSize - 1, 
									 MAX_CHAINLENGTH ) );

		status = krnlAcquireObject( iCertChain[ i ], OBJECT_TYPE_CERTIFICATE, 
									( MESSAGE_PTR_CAST ) &certChainPtr, 
									CRYPT_ERROR_SIGNALLED );
		if( cryptStatusError( status ) )
			return( status );
		ENSURES_OBJECT( sanityCheckCert( certChainPtr ), 
						certChainPtr->objectHandle );
		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;
		chainInfo[ i ].attributes = certChainPtr->attributes;
		status = getChainingAttribute( certChainPtr, 
									   CRYPT_CERTINFO_SUBJECTKEYIDENTIFIER,
									   &chainInfo[ i ].subjectKeyIdentifier,
									   &chainInfo[ i ].subjectKeyIDsize );
#ifdef USE_CERTLEVEL_PKIX_PARTIAL
		if( cryptStatusOK( status ) )
			{
			status = getChainingAttribute( certChainPtr, 
										   CRYPT_CERTINFO_AUTHORITY_KEYIDENTIFIER,
										   &chainInfo[ i ].issuerKeyIdentifier,
										   &chainInfo[ i ].issuerKeyIDsize );
			}
#endif /* USE_CERTLEVEL_PKIX_PARTIAL */
		krnlReleaseObject( certChainPtr->objectHandle );
		if( cryptStatusError( status ) )
			return( status );
		}
	ENSURES( LOOP_BOUND_OK );

	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 that it (or its successors) have issued until we 
   reach the end of the chain.  Returns the position of the leaf node in the 
   chain.

   In addition to finding just the (nominal) leaf certificate, the caller 
   can also specify a preferred certificate through its usage type, useful 
   when the "chain" is actually an arbitrary certificate collection 
   containing multiple leaf certificates.  This isn't quite as simple as it 
   seems because for usage = X alongside the standard case of a single leaf 
   certificate with usage = X we can also have a leaf certificate with usage 
   Y, two leaf certificates with usage X, or a CA certificate (but no leaf 
   certificate) with usage X.  To deal with this we use the caller-specified 
   usage as a preferred-certificate hint rather than an absolute selection 
   criterion, with the different cases illustrated as follows:

		  X		- Return this one.
	...../
		 \
		  Y

		  X
	...../
		 \
		  X		- Return this one (because of the way the algorithm is 
				  implemented, not by any specific policy decision).

		  Y
	...../
		 \
		  Y		- Return this one, same as above.

				 Y
	... CA+X .../
				\
				 Y	- Return this one.

   In other words we always try and return a leaf certificate if one exists, 
   and make the selection based on usage if possible.

   Finally, the usage is treated as an absolute match (all usages must 
   match) rather than a selective match (one usage of potentially several 
   must match).  In other words if the caller specifies usage X+Y then the 
   certificate must have both of those usages available */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1 ) ) \
static int findLeafNode( IN_ARRAY( certChainSize ) const CHAIN_INFO *chainInfo,
						 IN_RANGE( 1, MAX_CHAINLENGTH ) const int certChainSize,
						 IN_FLAGS_Z( KEYMGMT ) const int options )
	{
	const int requestedUsage = \
		( options == ( KEYMGMT_FLAG_USAGE_CRYPT | KEYMGMT_FLAG_USAGE_SIGN ) ) ? \
			CRYPT_KEYUSAGE_KEYENCIPHERMENT | CRYPT_KEYUSAGE_DIGITALSIGNATURE : \
		( options == KEYMGMT_FLAG_USAGE_CRYPT ) ? \
			CRYPT_KEYUSAGE_KEYENCIPHERMENT : \
		( options == KEYMGMT_FLAG_USAGE_SIGN ) ? \
			CRYPT_KEYUSAGE_DIGITALSIGNATURE : 0;
	LOOP_INDEX currentCertPos;
	int bestMatch = CRYPT_ERROR, optionalMatch;

	assert( isReadPtrDynamic( chainInfo, \
							  sizeof( CHAIN_INFO ) * certChainSize ) );

	REQUIRES( certChainSize > 0 && certChainSize <= MAX_CHAINLENGTH );
	REQUIRES( isFlagRangeZ( options, KEYMGMT ) && \
			  ( options & ~KEYMGMT_MASK_USAGEOPTIONS ) == 0 );

	/* If we don't find a better match, default to using the first 
	   certificate.  This is required in order to handle self-signed 
	   certificates, which are their own issuer and so never get passed to
	   the match-checking code.  Note that this can't handle sufficiently
	   perverse "chains" like one that contains two self-signed roots
	   with one having a signature usage and the other having an encryption
	   usage and the caller is asking for KEYMGMT_FLAG_USAGE_CRYPT, but
	   anything that weird shouldn't be expected to work properly in the
	   first place */
	optionalMatch = 0;

	/* Walk down the chain from the currently selected certificate checking 
	   for certificates issued by it until we can't go any further, with
	   optional filtering by certificate usage type.  
	   
	   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 */
	LOOP_EXT( currentCertPos = 0, currentCertPos < certChainSize, 
			  currentCertPos++, MAX_CHAINLENGTH )
		{
		CHAINING_INFO currentCertInfo;
		DATAPTR_ATTRIBUTE attributePtr;
		BOOLEAN certIsIssuer = FALSE;
		LOOP_INDEX_ALT childCertPos;
		int value, status;

		ENSURES( LOOP_INVARIANT_EXT( currentCertPos, 0, certChainSize - 1,
									 MAX_CHAINLENGTH ) );

		getSubjectChainingInfo( &currentCertInfo, 
								&chainInfo[ currentCertPos ] );

		/* Try and find a certificate issued by the current certificate */
		LOOP_EXT_ALT( childCertPos = 0, childCertPos < certChainSize, 
					  childCertPos++, MAX_CHAINLENGTH )
			{
			ENSURES( LOOP_INVARIANT_EXT_ALT( childCertPos, 0, certChainSize - 1,
											 MAX_CHAINLENGTH ) );

			/* 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( isIssuer( &currentCertInfo, &chainInfo[ childCertPos ] ) )
				{
				certIsIssuer = TRUE;
				break;
				}
			}
		ENSURES( LOOP_BOUND_OK_ALT );

		/* If the current certificate isn't a leaf certificate, continue to 
		   the next one */
		if( certIsIssuer )
			continue;

		/* If we're not selecting certificates based on a specific usage 
		   type, we're done */
		if( requestedUsage == KEYMGMT_FLAG_NONE )
			{
			bestMatch = optionalMatch = currentCertPos;
			continue;
			}

		/* Get the certificate's key usage */
		attributePtr = findAttributeField( chainInfo[ currentCertPos ].attributes,
										   CRYPT_CERTINFO_KEYUSAGE, 
										   CRYPT_ATTRIBUTE_NONE );
		if( DATAPTR_ISNULL( attributePtr ) )
			{
			/* There's no explicit key usage present, this certificate 
			   should be OK unless we find a more specific match */
			bestMatch = optionalMatch = currentCertPos;
			continue;
			}
		status = getAttributeDataValue( attributePtr, &value );
		if( cryptStatusError( status ) )
			continue;
		if( ( value & requestedUsage ) == requestedUsage )
			bestMatch = currentCertPos;
		else
			optionalMatch = currentCertPos;
		}
	ENSURES( LOOP_BOUND_OK );

	return( ( bestMatch != CRYPT_ERROR ) ? bestMatch : optionalMatch );
	}

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

CHECK_RETVAL_RANGE( 0, MAX_CHAINLENGTH ) 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 DUMMY_INIT, serialNumberSize;
	LOOP_INDEX i;
	int status;

	assert( isReadPtrDynamic( chainInfo, 
							  sizeof( CHAIN_INFO ) * certChainSize ) );
	assert( isReadPtrDynamic( 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 )
		{
		LOOP_EXT( i = 0, i < certChainSize, i++, MAX_CHAINLENGTH )
			{
			ENSURES( LOOP_INVARIANT_EXT( i, 0, certChainSize - 1,
										 MAX_CHAINLENGTH ) );

			if( matchSubjectKeyID( &chainInfo[ i ], keyID, keyIDlength ) )
				return( i );
			}
		ENSURES( LOOP_BOUND_OK );
		return( CRYPT_ERROR_NOTFOUND );
		}

	/* It's an issuerAndSerialNumber, extract the issuer DN and serial 
	   number */
	sMemConnect( &stream, keyID, keyIDlength );
	status = readSequence( &stream, NULL );
	if( cryptStatusOK( status ) )
		{
		status = getStreamObjectLength( &stream, &issuerDNsize, 
										MIN_DN_SIZE );
		}
	if( cryptStatusOK( status ) && !isShortIntegerRangeNZ( issuerDNsize ) )
		status = CRYPT_ERROR_BADDATA;
	if( cryptStatusOK( status ) )
		status = sMemGetDataBlock( &stream, &issuerDNptr, issuerDNsize );
	if( cryptStatusError( status ) )
		{
		sMemDisconnect( &stream );
		return( CRYPT_ERROR_NOTFOUND );
		}
	sSkip( &stream, issuerDNsize, MAX_INTLENGTH_SHORT );/* 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 */
	LOOP_EXT( i = 0, i < certChainSize, i++, MAX_CHAINLENGTH )
		{
		ENSURES( LOOP_INVARIANT_EXT( i, 0, certChainSize - 1,
									 MAX_CHAINLENGTH ) );

		if( matchIssuerDN( &chainInfo[ i ], issuerDNptr, issuerDNsize ) && \
			compareSerialNumber( chainInfo[ i ].serialNumber, 
								 chainInfo[ i ].serialNumberSize,
								 serialNumber, serialNumberSize ) )
			{
			return( i );
			}
		}
	ENSURES( LOOP_BOUND_OK );

	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 leafCert 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_PTR_OPT const CHAINING_INFO *chainingInfo,
						  IN_RANGE( CRYPT_UNUSED, MAX_CHAINLENGTH ) \
							const int leafCertEntry,
						  IN_HANDLE_OPT const CRYPT_CERTIFICATE leafCert,
						  IN_BOOL const BOOLEAN useStrictChaining )
	{
	CRYPT_CERTIFICATE orderedChain[ MAX_CHAINLENGTH + 8 ];
	CHAINING_INFO localChainingInfo;
	BOOLEAN chainInfoValid[ MAX_CHAINLENGTH + 8 ], moreMatches = TRUE;
	const int maxMatchLevel = useStrictChaining ? 1 : 0;
	LOOP_INDEX i;
	int orderedChainIndex;

	assert( isWritePtrDynamic( iCertChain, \
							   sizeof( CRYPT_CERTIFICATE ) * certChainSize ) );
	assert( isReadPtrDynamic( chainInfo, \
							  sizeof( CHAIN_INFO ) * certChainSize ) );
	assert( chainingInfo == NULL || \
			isReadPtr( chainingInfo, sizeof( CHAINING_INFO ) ) );

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

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

	/* Initially all chain entries except the one for the leaf certificate 
	   (defined either implicitly as the zero-th entry for leafCert or
	   explicitly as leafCertEntry) are valid */
	LOOP_EXT( i = 0, i < certChainSize, i++, MAX_CHAINLENGTH )
		{
		ENSURES( LOOP_INVARIANT_EXT( i, 0, certChainSize - 1,
									 MAX_CHAINLENGTH ) );

		chainInfoValid[ i ] = TRUE;
		}
	ENSURES( LOOP_BOUND_OK );

	/* If we're canonicalising an existing chain then there's a predefined 
	   chain start that we copy over, after which we can prepare to look for 
	   the next certificate up the chain */
	if( leafCert != CRYPT_UNUSED )
		{
		getIssuerChainingInfo( &localChainingInfo, &chainInfo[ 0 ] );
		orderedChain[ 0 ] = leafCert;
		chainInfoValid[ 0 ] = FALSE;
		orderedChainIndex = 1;
		}
	else
		{
		ENSURES( chainingInfo != NULL && leafCertEntry != CRYPT_UNUSED );
				 /* Keep static analysers happy */

		/* We're building a new chain, the caller has supplied the chaining
		   information */
		memcpy( &localChainingInfo, chainingInfo, sizeof( CHAINING_INFO ) );
		chainInfoValid[ leafCertEntry ] = FALSE;
		orderedChainIndex = 0;
		}

	/* Build an ordered chain of certificates from the leaf to the root */
	LOOP_MED_WHILE( moreMatches )
		{
		int matchLevel, LOOP_ITERATOR_ALT;

		ENSURES( LOOP_INVARIANT_MED_GENERIC() );

		/* 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 = 1), if that fails we fall back to a standard match 
		   (matchLevel = 0).  This is required to handle the significant 
		   number of CAs that don't get chaining by keyID right */
		REQUIRES( maxMatchLevel == 0 || maxMatchLevel == 1 );
		LOOP_EXT_REV_ALT( matchLevel = maxMatchLevel, \
						  !moreMatches && matchLevel >= 0, matchLevel--, 2 + 1 )
			{
			int LOOP_ITERATOR_ALT2;

			ENSURES( LOOP_INVARIANT_REV_ALT( matchLevel, 0, maxMatchLevel ) );

			LOOP_EXT_ALT2( i = 0, i < certChainSize, i++, MAX_CHAINLENGTH )
				{
				ENSURES( LOOP_INVARIANT_EXT_ALT2( i, 0, certChainSize - 1,
												  MAX_CHAINLENGTH ) );

				/* If this isn't the issuer, continue */
				if( !chainInfoValid[ i ] || \
					!isSubject( &localChainingInfo, &chainInfo[ i ], 
								matchLevel ? TRUE : FALSE ) )
					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 matchLevel loop as well */
				ENSURES( orderedChainIndex > 0 && \
						 orderedChainIndex <= certChainSize && \
						 orderedChainIndex < MAX_CHAINLENGTH );
				break;
				}
			ENSURES( LOOP_BOUND_OK_ALT2 );
			}
		ENSURES( LOOP_BOUND_EXT_REV_OK_ALT( 2 + 1 ) );
		}
	ENSURES( LOOP_BOUND_OK );

	/* If there are any certificates left, they're not needed for anything 
	   so we can free the resources */
	LOOP_EXT( i = 0, i < certChainSize, i++, MAX_CHAINLENGTH )
		{
		ENSURES( LOOP_INVARIANT_EXT( i, 0, certChainSize - 1,
									 MAX_CHAINLENGTH ) );

		if( chainInfoValid[ i ] )
			{
			krnlSendNotifier( iCertChain[ i ], IMESSAGE_DECREFCOUNT );
			chainInfoValid[ i ] = FALSE;
			}
		}
	ENSURES( LOOP_BOUND_OK );

	/* Replace the existing chain with the ordered version */
	LOOP_EXT( i = 0, i < certChainSize, i++, MAX_CHAINLENGTH )
		{
		ENSURES( LOOP_INVARIANT_EXT( i, 0, certChainSize - 1,
									 MAX_CHAINLENGTH ) );
		iCertChain[ i ] = CRYPT_ERROR;
		}
	ENSURES( LOOP_BOUND_OK );
	if( orderedChainIndex > 0 )
		{
		REQUIRES( rangeCheck( orderedChainIndex, 1, MAX_CHAINLENGTH - 1 ) );
		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,
						   IN_FLAGS( KEYMGMT ) const int options )
	{
	CHAIN_INFO chainInfo[ MAX_CHAINLENGTH + 8 ];
	CERT_INFO *certChainPtr;
	CHAINING_INFO chainingInfo;
	const int keyUsageOptions = options & KEYMGMT_MASK_USAGEOPTIONS;
	int leafNodePos, newCertChainEnd, complianceLevel, status;

	assert( isWritePtr( iLeafCert, sizeof( CRYPT_CERTIFICATE ) ) );
	assert( isWritePtrDynamic( iCertChain, \
							   sizeof( CRYPT_CERTIFICATE ) * certChainEnd ) );
	assert( keyID == NULL || isReadPtrDynamic( 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 ) );
	REQUIRES( isFlagRangeZ( options, KEYMGMT ) && \
			  ( options & ~KEYMGMT_MASK_CERTOPTIONS ) == 0 );
	REQUIRES( ( keyIDtype == CRYPT_KEYID_NONE && \
				keyUsageOptions == KEYMGMT_FLAG_NONE ) || \
			  ( keyIDtype != CRYPT_KEYID_NONE && \
				keyUsageOptions == KEYMGMT_FLAG_NONE ) || \
			  ( keyIDtype == CRYPT_KEYID_NONE && \
				keyUsageOptions != KEYMGMT_FLAG_NONE ) );

	/* 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 )
		{
		status = leafNodePos = \
					findIdentifiedLeafNode( chainInfo, certChainEnd,
											keyIDtype, keyID, keyIDlength );
		}
	else
		{
		status = leafNodePos = \
					findLeafNode( chainInfo, certChainEnd, keyUsageOptions );
		}
	if( cryptStatusError( status ) )
		return( status );
	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, &chainingInfo, leafNodePos, CRYPT_UNUSED,
					( 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 having been 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 )
		{
		LOOP_INDEX i;

		LOOP_EXT( i = 0, i < newCertChainEnd - 1, i++, MAX_CHAINLENGTH )
			{
			CERT_INFO *certInfoPtr;
			BOOLEAN_INT value;

			ENSURES( LOOP_INVARIANT_EXT( i, 0, newCertChainEnd - 2,
										 MAX_CHAINLENGTH ) );

			/* 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, 
										( MESSAGE_PTR_CAST ) &certInfoPtr, 
										CRYPT_ERROR_SIGNALLED );
			if( cryptStatusError( status ) )
				continue;
			ENSURES_OBJECT( sanityCheckCert( certInfoPtr ),
							certInfoPtr->objectHandle );
			CLEAR_FLAG( certInfoPtr->flags, CERT_FLAG_SELFSIGNED );
			SET_FLAG( certInfoPtr->flags, CERT_FLAG_PATHKLUDGE );
			krnlReleaseObject( certInfoPtr->objectHandle );
			}
		ENSURES( LOOP_BOUND_OK );
		}
#endif /* USE_CERTLEVEL_PKIX_FULL */

	/* Since the objects that make up the chain were imported as individual 
	   certificates because at the time of import we didn't know which one 
	   was the leaf, we have to convert the leaf's object-type from 
	   certificate to certificate chain */
	status = convertCertToChain( iLeafCert, *iLeafCert,
								 ( options & KEYMGMT_FLAG_DATAONLY_CERT ) ? \
								   TRUE : FALSE );
	if( cryptStatusError( status ) )
		return( status );

	/* 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, 
								( MESSAGE_PTR_CAST ) &certChainPtr, 
								CRYPT_ERROR_SIGNALLED );
	if( cryptStatusError( status ) )
		return( status );
	ENSURES_OBJECT( sanityCheckCert( certChainPtr ), 
					certChainPtr->objectHandle );
	REQUIRES_OBJECT( rangeCheck( newCertChainEnd, 1, MAX_CHAINLENGTH - 1 ),
					 certChainPtr->objectHandle );
	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;
	LOOP_INDEX i;
	int 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_SHA1 );
	if( cryptStatusError( status ) )
		return( FALSE );

	/* Make sure that it isn't already present in the collection */
	LOOP_EXT( i = 0, i < certChainLen, i++, MAX_CHAINLENGTH )
		{
		ENSURES_B( LOOP_INVARIANT_EXT( i, 0, certChainLen - 1,
									   MAX_CHAINLENGTH ) );

		if( !memcmp( certChainHashes[ i ], 
					 certChainHashes[ certChainLen ], msgData.length ) )
			return( TRUE );
		}
	ENSURES_B( LOOP_BOUND_OK );

	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_PTR CERT_INFO *certInfoPtr, 
				   IN_HANDLE const CRYPT_HANDLE certChain,
				   IN_BOOL 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;
	LOOP_INDEX i;
	int status;

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

	REQUIRES( sanityCheckCert( certInfoPtr ) );
	REQUIRES( isHandleRangeValid( certChain ) );
	REQUIRES( isBooleanValue( isCertCollection ) );

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

	/* If we're building a certificate collection then all that we need to 
	   ensure is that there are no duplicate certificates rather than having 
	   a strict chain.  To handle duplicate checking we build a list of the 
	   fingerprints for each certificate in the chain */
	LOOP_EXT( i = 0, i < MAX_CHAINLENGTH + 1, i++,
			  MAX_CHAINLENGTH + 2 )
		{
		ENSURES( LOOP_INVARIANT_EXT( i, 0, MAX_CHAINLENGTH,
									 MAX_CHAINLENGTH + 2 ) );

		memset( certChainHashes[ i ], 0, CRYPT_MAX_HASHSIZE );
		}
	ENSURES( LOOP_BOUND_OK );
	if( isCertCollection )
		{
		LOOP_EXT( i = 0, i < destCertChainInfo->chainEnd, i++, 
				  MAX_CHAINLENGTH )
			{
			MESSAGE_DATA msgData;

			ENSURES( LOOP_INVARIANT_EXT( i, 0, 
										 destCertChainInfo->chainEnd - 1,
										 MAX_CHAINLENGTH ) );

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

	/* 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, 
								( MESSAGE_PTR_CAST ) &chainCertInfoPtr, 
								CRYPT_ERROR_SIGNALLED );
	if( cryptStatusError( status ) )
		return( status );
	ENSURES_OBJECT( sanityCheckCert( chainCertInfoPtr ),
					chainCertInfoPtr->objectHandle );
	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 */
	LOOP_EXT( i = 0, i < srcCertChainInfo->chainEnd, i++, MAX_CHAINLENGTH )
		{
		const CRYPT_CERTIFICATE iCopyCert = srcCertChainInfo->chain[ i ];

		ENSURES_OBJECT( LOOP_INVARIANT_EXT( i, 0, \
											srcCertChainInfo->chainEnd - 1,
											MAX_CHAINLENGTH ),
						chainCertInfoPtr->objectHandle );

		/* 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_OBJECT( LOOP_BOUND_OK, chainCertInfoPtr->objectHandle );
	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 )
		{
		SET_FLAG( 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, NULL, 
						   CRYPT_UNUSED, iChainCert, FALSE ) );
	}

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

/* Read a single certificate in a chain */

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

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

	REQUIRES( iCryptOwner == DEFAULTUSER_OBJECT_HANDLE || \
			  isHandleRangeValid( iCryptOwner ) );
	REQUIRES( type == CRYPT_CERTTYPE_CERTCHAIN || \
			  type == CRYPT_ICERTTYPE_CMS_CERTSET || \
			  type == CRYPT_ICERTTYPE_CMP_CERTSEQUENCE || \
			  type == CRYPT_ICERTTYPE_TLS_CERTCHAIN || \
			  type == CRYPT_ICERTTYPE_TLS13_CERTCHAIN );
	REQUIRES( isBooleanValue( dataOnlyCert ) );
	REQUIRES( isBooleanValue( isIndefiniteLength ) );

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

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

	/* Find out how large the certificate data is and make sure that the 
	   size is approximately valid before we pass it on to other 
	   functions */
	status = getStreamObjectLength( stream, &length, MIN_CERTSIZE );
	if( cryptStatusError( status ) )
		return( status );
	if( !isShortIntegerRange( length ) )
		return( CRYPT_ERROR_BADDATA );

	/* Since TLS certificate chains contain certificates interspersed with 
	   non-certificate TLS 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_TLS_CERTCHAIN || \
		type == CRYPT_ICERTTYPE_TLS13_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 ) )
				status = checkCertObjectEncoding( certDataPtr, length );
			}
		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,
								   CRYPT_CERTTYPE_CERTIFICATE, length,
								   dataOnlyCert ? KEYMGMT_FLAG_DATAONLY_CERT : \
												  KEYMGMT_FLAG_NONE,
								   errorInfo );
	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 );
			}
		}

	/* TLS 1.3 added TLS-style extensions to the certificate extensions 
	   because there wasn't enough extensibility already present, so we skip
	   any junk tacked onto the end of the certificate */
#ifdef USE_TLS13
	if( type == CRYPT_ICERTTYPE_TLS13_CERTCHAIN )
		{
		status = length = readUint16( stream );
		if( !cryptStatusError( status ) && length > 0 )
			status = sSkip( stream, length, MAX_INTLENGTH_SHORT );
		if( cryptStatusError( status ) )
			return( status );
		}
#endif /* USE_TLS13 */

	return( CRYPT_OK );
	}

/* Read certificate chain/sequence information.  Returning extended error 
   information from this function ins't possible because there's no 
   certificate object to associate it with.  That is, while assembling the 
   chain we don't know which one is the container for the chain, so we don't 
   know which one to set error information for.  Because of this the best 
   that we can do is DEBUG_DIAG() the error report */

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2, 9 ) ) \
int readCertChain( INOUT_PTR 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,
				   IN_FLAGS( KEYMGMT ) const int options,
				   INOUT_PTR ERROR_INFO *errorInfo )
	{
	CRYPT_CERTIFICATE iCertChain[ MAX_CHAINLENGTH + 8 ];
	const BOOLEAN dataOnlyCert = ( options & KEYMGMT_FLAG_DATAONLY_CERT ) ? \
								   TRUE : FALSE;
	int certSequenceLength DUMMY_INIT, endPos = 0, certChainEnd = 0;
	int status = CRYPT_OK, LOOP_ITERATOR;

	assert( isWritePtr( stream, sizeof( STREAM ) ) );
	assert( isWritePtr( iCryptCert, sizeof( CRYPT_CERTIFICATE ) ) );
	assert( keyID == NULL || isReadPtrDynamic( keyID, keyIDlength ) );
	assert( isWritePtr( errorInfo, sizeof( ERROR_INFO ) ) );

	REQUIRES( iCryptOwner == DEFAULTUSER_OBJECT_HANDLE || \
			  isHandleRangeValid( iCryptOwner ) );
	REQUIRES( type == CRYPT_CERTTYPE_CERTCHAIN || \
			  type == CRYPT_ICERTTYPE_CMS_CERTSET || \
			  type == CRYPT_ICERTTYPE_CMP_CERTSEQUENCE || \
			  type == CRYPT_ICERTTYPE_TLS_CERTCHAIN || \
			  type == CRYPT_ICERTTYPE_TLS13_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 ) );
	REQUIRES( isFlagRangeZ( options, KEYMGMT ) && \
			  ( options & ~( KEYMGMT_MASK_USAGEOPTIONS | \
							 KEYMGMT_MASK_CERTOPTIONS ) ) == 0 );
	REQUIRES( ( keyIDtype == CRYPT_KEYID_NONE && \
				options == KEYMGMT_FLAG_NONE ) || \
			  ( keyIDtype != CRYPT_KEYID_NONE && \
				options == KEYMGMT_FLAG_NONE ) || \
			  ( keyIDtype == CRYPT_KEYID_NONE && \
				options != KEYMGMT_FLAG_NONE ) );

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

	switch( type )
		{
		case CRYPT_CERTTYPE_CERTCHAIN:
		case CRYPT_ICERTTYPE_TLS_CERTCHAIN:
		case CRYPT_ICERTTYPE_TLS13_CERTCHAIN:
			/* For a standard certificate chain the outer wrapper has already been 
			   read by the caller so the certificate chain is everything that's left.
			   For an TLS certificate chain there's no outer wrapper to give us 
			   length information, however the length will be equal to the total 
			   remaining stream size */
			certSequenceLength = sMemDataLeft( stream );
			break;

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

		case CRYPT_ICERTTYPE_CMP_CERTSEQUENCE:
			status = readSequence( stream, &certSequenceLength );
			break;

		default:
			retIntError();
		}
	if( cryptStatusError( status ) )
		{
		retExt( status,
				( status, errorInfo,
				  "Invalid %s wrapper", getCertTypeNameLC( type ) ) );
		}
	ENSURES( ( certSequenceLength == CRYPT_UNUSED ) || \
			 isShortIntegerRangeNZ( certSequenceLength ) );

	/* If it's a definite-length chain, determine where it ends */
	if( certSequenceLength != CRYPT_UNUSED )
		{
		endPos = stell( stream ) + certSequenceLength;
		ENSURES( isIntegerRangeMin( endPos, 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 */
	LOOP_MED_WHILE( certSequenceLength == CRYPT_UNUSED || \
					stell( stream ) <= endPos - MIN_ATTRIBUTE_SIZE )
		{
		CRYPT_CERTIFICATE iNewCert DUMMY_INIT;
		ERROR_INFO localErrorInfo;

		ENSURES( LOOP_INVARIANT_MED_GENERIC() );

		/* Make sure that we don't overflow the chain.  Note that the chain-
		   size check is triggered as soon as we reach MAX_CHAINLENGTH (even
		   though it's coded as a more generic '>='), so we always pass a
		   valid chain-size value to freeCertChain() */
		if( certChainEnd >= MAX_CHAINLENGTH )
			{
			freeCertChain( iCertChain, certChainEnd );
			retExt( CRYPT_ERROR_OVERFLOW,
					( CRYPT_ERROR_OVERFLOW, errorInfo,
					  "%s contains more than %d certificates", 
					  getCertTypeName( type ), MAX_CHAINLENGTH ) );
			}

		/* Read the next certificate in the chain */
		clearErrorInfo( &localErrorInfo );
		status = readSingleCert( stream, &iNewCert, iCryptOwner, type, 
								 dataOnlyCert,
								 ( certSequenceLength == CRYPT_UNUSED ) ? \
									TRUE : FALSE, &localErrorInfo );
		if( cryptStatusError( status ) && status != OK_SPECIAL )
			{
			if( certChainEnd > 0 )
				freeCertChain( iCertChain, certChainEnd );
			retExtErr( status,
					   ( status, errorInfo, &localErrorInfo,
					     "Invalid %s entry #%d", 
						 getCertTypeNameLC( type ), certChainEnd ) );
			}
		iCertChain[ certChainEnd++ ] = iNewCert;
		if( status == OK_SPECIAL )
			break;	/* We've reached the end of the chain */
		}
	ENSURES( LOOP_BOUND_OK );

	/* We must have read at least one certificate in order to create a 
	   chain */
	if( certChainEnd <= 0 )
		{
		retExt( CRYPT_ERROR_BADDATA,
				( CRYPT_ERROR_BADDATA, errorInfo,
				  "%s doesn't contain any certificates", 
				  getCertTypeName( type ) ) );
		}

	/* Build the complete chain from the individual certificates */
	status = buildCertChain( iCryptCert, iCertChain, certChainEnd, 
							 keyIDtype, keyID, keyIDlength, options );
	if( cryptStatusError( status ) )
		{
		freeCertChain( iCertChain, certChainEnd );
		retExt( status,
				( status, errorInfo,
				  "Couldn't build %s from individual certificates", 
				  getCertTypeName( type ) ) );
		}

	return( CRYPT_OK );
	}

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

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 4, 7 ) ) \
int assembleCertChain( OUT_HANDLE_OPT 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,
					   INOUT_PTR ERROR_INFO *errorInfo )
	{
	CRYPT_CERTIFICATE iCertSet[ MAX_CHAINLENGTH + 8 ], iCertChain, lastCert;
	MESSAGE_KEYMGMT_INFO getnextcertInfo;
	const int chainOptions = options & KEYMGMT_FLAG_DATAONLY_CERT;
	int stateInfo = CRYPT_ERROR, certSetSize = 1;
	int status, LOOP_ITERATOR;

	assert( isWritePtr( iCertificate, sizeof( CRYPT_CERTIFICATE ) ) );
	assert( isReadPtrDynamic( keyID, keyIDlength ) );
	assert( isWritePtr( errorInfo, sizeof( ERROR_INFO ) ) );

	REQUIRES( isHandleRangeValid( iCertSource ) );
	REQUIRES( isEnumRange( keyIDtype, CRYPT_KEYID ) );
	REQUIRES( keyIDlength > 0 && keyIDlength < MAX_ATTRIBUTE_SIZE );
			  /* The keyID can be an arbitrary value, including ones from
				 PKCS #11 devices, so it can be as little as a single byte */
	REQUIRES( isFlagRangeZ( options, KEYMGMT ) && \
			  ( options & ~KEYMGMT_MASK_CERTOPTIONS ) == 0 );

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

	/* 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 ) )
		{
		retExtObj( status,
				   ( status, errorInfo, iCertSource,
					 "Couldn't read initial certificate in chain from data "
					 "source" ) );
		}
	iCertSet[ 0 ] = lastCert = getnextcertInfo.cryptHandle;

	/* Make sure that the data source that we're using actually gave us what
	   we asked for.  The one situation where we can't do this is when we've
	   been given a key ID and we're looking up a data-only certificate, 
	   since the IDs aren't present in the certificate but are generated 
	   dynamically in the associated context */
	if( !( ( keyIDtype == CRYPT_IKEYID_KEYID || \
			 keyIDtype == CRYPT_IKEYID_PGPKEYID ) && \
		   ( options & KEYMGMT_FLAG_DATAONLY_CERT ) ) )
		{
		status = iCryptVerifyID( lastCert, keyIDtype, keyID, keyIDlength );
		if( cryptStatusError( status ) )
			{
			krnlSendNotifier( lastCert, IMESSAGE_DECREFCOUNT );
			retExt( status,
					( status, errorInfo, 
					  "Certificate identity information doesn't match the "
					  "ID used to read it from a data source" ) );
			}
		}

	/* 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 */
	setMessageKeymgmtInfo( &getnextcertInfo, CRYPT_KEYID_NONE, NULL, 0, 
						   &stateInfo, sizeof( int ), chainOptions );
	LOOP_MED_WHILE( cryptStatusOK( status ) )
		{
		BOOLEAN_INT selfSigned;

		ENSURES( LOOP_INVARIANT_MED_GENERIC() );

		/* 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 == TRUE )
			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 then 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( certSetSize >= MAX_CHAINLENGTH )
			{
			krnlSendNotifier( getnextcertInfo.cryptHandle,
							  IMESSAGE_DECREFCOUNT );
			freeCertChain( iCertSet, certSetSize );
			retExt( CRYPT_ERROR_OVERFLOW,
					( CRYPT_ERROR_OVERFLOW, errorInfo, 
					   "Certificate chain contains more than %d "
					   "certificates", MAX_CHAINLENGTH ));
			}

		iCertSet[ certSetSize++ ] = lastCert = getnextcertInfo.cryptHandle;
		}
	ENSURES( LOOP_BOUND_OK );
	if( cryptStatusError( status ) )
		{
		freeCertChain( iCertSet, certSetSize );
		retExtObj( status,
				   ( status, errorInfo, iCertSource,
					 "Couldn't read certificate #%d in chain from data "
					 "source", certSetSize ) );
		}

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

	*iCertificate = iCertChain;
	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, TLS requires that we return component-by-
   component lengths that need to be inserted as 24-bit (3 byte) values 
   between each certificate, and TLS 1.3 adds an additional 16-bit all-zero
   value after the certificate.  To handle this we take as an optional 
   parameter an array used to store the individual path component lengths
   and then insert the interstitial values when we write the certificates */

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,
						   IN_ENUM( CRYPT_CERTFORMAT ) \
								const CRYPT_CERTFORMAT_TYPE certFormatType )
	{
	CERT_CERT_INFO *certChainInfo = certInfoPtr->cCertCert;
	const BOOLEAN extraLength = \
		( certFormatType == CRYPT_ICERTFORMAT_TLS_CERTCHAIN ) ? 3 : \
		( certFormatType == CRYPT_ICERTFORMAT_TLS13_CERTCHAIN ) ? 5 : 0;
	LOOP_INDEX i;
	int length = 0;

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

	REQUIRES( ( ( certFormatType == CRYPT_CERTFORMAT_CERTCHAIN || \
				  certFormatType == CRYPT_ICERTFORMAT_CERTSET || \
				  certFormatType == CRYPT_ICERTFORMAT_CERTSEQUENCE ) && \
				  certSizeInfo == NULL ) || \
			  ( ( certFormatType == CRYPT_ICERTFORMAT_TLS_CERTCHAIN || \
				  certFormatType == CRYPT_ICERTFORMAT_TLS13_CERTCHAIN ) && \
				  certSizeInfo != NULL ) );

	/* 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( !TEST_FLAG( certInfoPtr->flags, CERT_FLAG_CERTCOLLECTION ) )
		length = certInfoPtr->certificateSize + extraLength;
	LOOP_EXT( i = 0, i < certChainInfo->chainEnd, i++, MAX_CHAINLENGTH )
		{
		MESSAGE_DATA msgData;
		int status;

		ENSURES( LOOP_INVARIANT_EXT( i, 0, certChainInfo->chainEnd - 1,
									 MAX_CHAINLENGTH ) );

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

	return( CRYPT_OK );
	}

CHECK_RETVAL STDC_NONNULL_ARG( ( 1, 2 ) ) \
static int writeCertPath( INOUT_PTR STREAM *stream, 
						  const CERT_INFO *certInfoPtr,
						  IN_ARRAY_OPT_C( MAX_CHAINLENGTH ) \
								const int *certSizeInfo,
						  IN_ENUM( CRYPT_CERTFORMAT ) \
								const CRYPT_CERTFORMAT_TYPE certFormatType )
	{
	CERT_CERT_INFO *certChainInfo = certInfoPtr->cCertCert;
	LOOP_INDEX i;
	int status = CRYPT_OK;

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

	REQUIRES( ( ( certFormatType == CRYPT_CERTFORMAT_CERTCHAIN || \
				  certFormatType == CRYPT_ICERTFORMAT_CERTSET || \
				  certFormatType == CRYPT_ICERTFORMAT_CERTSEQUENCE ) && \
				  certSizeInfo == NULL ) || \
			  ( ( certFormatType == CRYPT_ICERTFORMAT_TLS_CERTCHAIN || \
				  certFormatType == CRYPT_ICERTFORMAT_TLS13_CERTCHAIN ) && \
				  certSizeInfo != NULL ) );

	/* 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( !TEST_FLAG( certInfoPtr->flags, CERT_FLAG_CERTCOLLECTION ) )
		{
		if( certFormatType == CRYPT_ICERTFORMAT_TLS_CERTCHAIN || \
			certFormatType == CRYPT_ICERTFORMAT_TLS13_CERTCHAIN ) 
			{
			sputc( stream, 0 );		/* 24-bit length */
			writeUint16( stream, certInfoPtr->certificateSize );
			}
		status = swrite( stream, certInfoPtr->certificate, 
						 certInfoPtr->certificateSize );
		if( cryptStatusOK( status ) && \
			certFormatType == CRYPT_ICERTFORMAT_TLS13_CERTCHAIN )
			status = writeUint16( stream, 0 );
		}
	LOOP_EXT( i = 0, 
			  i < certChainInfo->chainEnd && cryptStatusOK( status ),
			  i++, MAX_CHAINLENGTH )
		{
		ENSURES( LOOP_INVARIANT_EXT( i, 0, certChainInfo->chainEnd - 1,
									 MAX_CHAINLENGTH ) );

		if( certFormatType == CRYPT_ICERTFORMAT_TLS_CERTCHAIN || \
			certFormatType == CRYPT_ICERTFORMAT_TLS13_CERTCHAIN ) 
			{
			sputc( stream, 0 );		/* 24-bit length */
			status = writeUint16( stream, certSizeInfo[ i ] );
			if( cryptStatusError( status ) )
				break;
			}
		status = exportCertToStream( stream, certChainInfo->chain[ i ], 
									 CRYPT_CERTFORMAT_CERTIFICATE );
		if( cryptStatusOK( status ) && \
			certFormatType == CRYPT_ICERTFORMAT_TLS13_CERTCHAIN )
			status = writeUint16( stream, 0 );
		}
	ENSURES( LOOP_BOUND_OK );

	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_LENGTH STDC_NONNULL_ARG( ( 1 ) ) \
int sizeofCertCollection( IN_PTR const CERT_INFO *certInfoPtr,
						  IN_ENUM( CRYPT_CERTFORMAT ) \
							const CRYPT_CERTFORMAT_TYPE certFormatType )
	{
	int length, status;

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

	REQUIRES( sanityCheckCert( certInfoPtr ) );
	REQUIRES( certFormatType == CRYPT_ICERTFORMAT_CERTSET || \
			  certFormatType == CRYPT_ICERTFORMAT_CERTSEQUENCE || \
			  certFormatType == CRYPT_ICERTFORMAT_TLS_CERTCHAIN || \
			  certFormatType == CRYPT_ICERTFORMAT_TLS13_CERTCHAIN );

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

		status = sizeofCertPath( certInfoPtr, &length, certSizeInfo,
								 certFormatType );
		}
	else
		{
		/* It's a standard PKCS #7/CMS chain */
		status = sizeofCertPath( certInfoPtr, &length, NULL,
								 certFormatType );
		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_PTR STREAM *stream, 
						 IN_PTR const CERT_INFO *certInfoPtr,
						 IN_ENUM( CRYPT_CERTFORMAT ) \
							const CRYPT_CERTFORMAT_TYPE certFormatType )
	{
	int certSizeInfo[ MAX_CHAINLENGTH + 8 ];
	int *certSizePtr = \
			( certFormatType == CRYPT_ICERTFORMAT_TLS_CERTCHAIN || \
			  certFormatType == CRYPT_ICERTFORMAT_TLS13_CERTCHAIN ) ? \
			certSizeInfo : NULL;
	int certCollectionLength, status;

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

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

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

		case CRYPT_ICERTFORMAT_TLS_CERTCHAIN:
		case CRYPT_ICERTFORMAT_TLS13_CERTCHAIN:
			status = CRYPT_OK;
			break;

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

	return( writeCertPath( stream, certInfoPtr, certSizePtr, 
						   certFormatType ) );
	}

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

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

	REQUIRES( sanityCheckCert( certInfoPtr ) );

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

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

	/* Write the outer SEQUENCE wrapper, contentType, and content wrapper */
	writeSequence( stream, 
				   sizeofOID( OID_CMS_SIGNEDDATA ) + \
					sizeofShortObject( sizeofShortObject( innerLength ) ) );
	swrite( stream, OID_CMS_SIGNEDDATA, sizeofOID( OID_CMS_SIGNEDDATA ) );
	writeConstructed( stream, sizeofShortObject( innerLength ), 0 );
	status = writeSequence( stream, innerLength );
	if( cryptStatusError( status ) )
		return( status );

	/* 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 ) );
	status = writeConstructed( stream, certSetLength, 0 );
	if( cryptStatusOK( status ) )
		{
		status = writeCertPath( stream, certInfoPtr, NULL, 
								CRYPT_CERTFORMAT_CERTCHAIN );
		}
	if( cryptStatusOK( status ) )
		status = writeSet( stream, 0 );
	return( status );
	}
#endif /* USE_CERTIFICATES */
