pgptrustprop.c

可以实现对邮件的加密解密以及签名

/*____________________________________________________________________________
        Copyright (C) 2002 PGP Corporation
        All rights reserved.

		Perform the trust propagation pass over a keyring
		
        $Id: pgpTrustProp.c,v 1.39 2002/08/06 20:11:00 dallen Exp $
____________________________________________________________________________*/
#include "pgpConfig.h"

#include <time.h>
#include <stddef.h>

#include "pgpDebug.h"
#include "pgpMakeSig.h"
#include "pgpMem.h"
#include "pgpEnv.h"
#include "pgpPktByte.h"
#include "pgpRegExp.h"
#include "pgpKeyPriv.h"
#include "pgpTimeDate.h"
#include "pgpTrustPriv.h"
#include "pgpHashPriv.h"
#include "pgpErrors.h"
#include "pgpPubKey.h"
#include "pgpSig.h"
#include "pgpSigSpec.h"
#include "pgpUsuals.h"
#include "pgpTypes.h"
#include "pgpX509Priv.h"

#ifndef NULL
#define NULL 0
#endif

/*
 * This symbol marks code which prints the progress of the maintenance
 * pass.  That code assumes stdio, which is not portable across GUIs, so
 * something will need to be done about it.  The prints are left in the
 * source to make the location of the replacements obvious.  The code
 * assumes a non-existent "FILE *f" to print to, so just #defining this
 * symbol will NOT work.
 */
#undef PRINT_PROGRESS

/*
 * The trust models...
 * All models start from a number of axiomatic "the buck stops here"
 * keys.  These are the keys owned by the PGP user.  This is the
 * initial set of trusted keys.  Each key has a trust value - a
 * level of confidence that the user places in signatures made by
 * that key.
 * 
 * -- The new trust model
 *
 * This is based on a much more rigorous treatment of trust by Ueli
 * Maurer.  See "Modelling a Public-Key Infrastructure", Ueli Maurer,
 * Proceedings 1996 European Symposium on Research in Computer Security
 * (ESORICS '96), E. Bertino (Ed.), Lecture Notes in Computer Science,
 * Berlin: Springer-Verlag, Rome, Italy, Sept. 1996.  Also available from
 * <URL: http://www.inf.ethz.ch/personal/maurer/publications>.
 *
 * Consider the graph formed by taking each key as a node and
 * each signature as an edge, and assign each signature an independent
 * probability of being correct.  (The probabilities don't have to be
 * independent, but it gets messy fast if they aren't, so the possibility
 * isn't considered any further.)  For each possible combination of
 * valid and invalid signatures, assign it a probability based on the
 * probability of each signature being correct, and if there is a path
 * of valid signatures from the root set to a given userid, it is correct.
 * Add up the probabilities of all the cases in which the userid is correct,
 * and you have the computed probability that the userid is correct.
 *
 *
 * This implements the basic Maurer trust model fairly literally.  The
 * Maurer model is often considered to be "intractably complex" (an
 * out of context quote from his paper), but with certain
 * simplifications it should be feasible:
 *
 * - Focus on on-the-fly validation so we only have to find the validity of
 *   a single key.
 * - Search for paths from the target key back to an axiomatic key such that
 *   all keys on the path are trusted introducers (nonzero confidence).
 * - Limit this search by a depth constraint, and possibly limit the total
 *   number of nodes we will look at if the depth constraint is inadequate.
 * - Find the basic trust contribution of each of the resulting paths (not yet
 *   considering interactions) as the product of the trust of each segment on
 *   the path.
 * - Sort the paths by this value and prune to keep just the top 10 or
 *   so paths.
 * - Apply Maurer's algorithm, considering all subsets of paths (2**n of them,
 *   where n is the number of paths).  For each subset, form the union of all
 *   segments on the paths in that subset, and take the product of the segment
 *   trusts.  Subsets with an odd number of paths add confidence, those with an
 *   even number of paths subtract.
 *
 * By limiting ourselves to just the trusted introducers (plus one
 * other) the total number of keys to be considered should not become
 * too large.  Given practical and customary limitations on the number
 * of signatures a key will usually have, it should be possible to
 * find paths back to the axiomatic keys in a reasonable amount of
 * time, especially if the algorithm only needs to be run for a single
 * key (or a small number of keys) when we encrypt or check a
 * signature.  Then when we prune the list of paths to just the top
 * 10, we should still be able to get a reasonably accurate
 * (under)estimate of the actual trust, unless the key gained trust by
 * having a large number of paths each with only a small amount of
 * trust.  That case must be neglected for efficiency in this
 * algorithm.  Having pruned the paths to a small enough set we can
 * then apply Maurer's algorithm efficiently.
 *
 * There is an additional complication specific to the PGP trust
 * model.  Maurer's algorithm is expressed in terms of paths where
 * each segment has an associated trust level.  These trusts are
 * described in PGP as user-defined confidence levels specified for
 * the userid(s) on a key.  This means that the output of the
 * calculation above is a validity value for a particular userid on a
 * key, based on the signatures on that userid.  The inputs need to be
 * based on the user defined confidence values for the userids.  The
 * complication arises for keys which have more than one userid
 * with different user-defined confidence levels.  It is not clear how
 * to map this situation to Maurer's trust model.
 *
 * For keys with only one userid, the confidence of that userid is used.
 * If there is more than one userid, a conservative approach is to use
 * the userid with the smallest user-defined confidence value.  (Userids
 * for which the user has not specified a confidence level do not
 * enter into this calculation.)  If all of the userids (of those with
 * non-zero confidence) have validity values (from earlier runs of the
 * trust calculation) then we can choose the confidence of the userid
 * with the highest validity as in the previous trust model.
 *
 * Not all of the optimizations above are implemented in the current
 * code, nor has it been thoroughly tested.  In particular, the
 * trustprop function is still used and tries to run the algorithm on
 * all keys in the set.  Although a depth limitation is used there is
 * no other way of limiting the construction of the paths.
 *
 * Some further ideas for improvement:
 *
 * - Paths don't need to include the last step to the trusted
 *   introducer, since that always has confidence of 1.0.
 *
 * - For creating the path subset unions, a linear search for overlap
 *   is used now.  This may be OK for short paths but a more efficient
 *   algorithm would be better.  Perhaps a hash table for path segments
 *   in the subset would be worthwhile.
 *
 * - When adding/subtracting the pathconf values, maybe it would be
 *   better to accumulate 1-confidence rather than confidence?  I am
 *   worried about roundoff error for values very close to 1.0.
 *
 * - Could use a Gray code to go through path subsets in a sequence
 *   which would alternate even and odd parity subsets, so we would
 *   alternately add and subtract trust.  This might help with
 *   accuracy.  (A Gray code is a binary counter which has the property
 *   that only one bit changes each step.  One example is:
 *   ++j, i ^= j & (j ^ (j-1)); which counts j as a regular counter and
 *   i as a Gray code counter.)
 */


static PGPBoolean
sKeyHasConfidence (PGPKeyDBObj *key);


/********************** REGEXP Support ***************************/


/* Clear key regexp pointers */
	static void
mntClearKeyRegexps( PGPKeyDB *db )
{
	PGPKeyDBObj *key;
	PGPKeyInfo *kinfo;

	for (key = db->firstKeyInDB; IsntNull(key); key = key->next) {
		if( !pgpKeyDBObjIsReal( key ) )
			continue;
		kinfo = pgpKeyToKeyInfo( key );
		kinfo->regexp = NULL;
	}
}




/* Check whether a sig is made illegal due to regexp considerations.
 * return TRUE if OK, FALSE if not.  If we have some error handling the regexp,
 * we say the sig is not OK.
 */
	static PGPBoolean
mntSigOKWithRegexpOnSigner( PGPKeyDBObj const *sig, PGPKeyDBObj *signer )
{
	PGPKeyDBObj *parent;
	PGPKeyInfo *kinfo;
	char const *udata;
	PGPSize len;
	PGPSize hlen;
	int rslt;

	pgpAssert( OBJISSIG( sig ) );

	/* See if signing key got its trust conditioned with a regexp */
	if( !pgpKeyDBObjIsReal( signer ) )
		return TRUE;
	pgpAssert( OBJISKEY( signer ) );
	kinfo = pgpKeyToKeyInfo( signer );
	if( IsNull( kinfo->regexp ) )
		return TRUE;

	/* Can only handle sigs on userids for regexps */
	parent = sig->up;
	if( !OBJISUSERID(parent) )
		return FALSE;

	/* See if userid matches regexp */
	udata = (const char *) pgpFetchObject( parent, &len );
	hlen = pgpPktBufferHeaderLen( (PGPByte *) udata );

	rslt = pgpRegExec( (regexp *)kinfo->regexp, udata+hlen );
	if( rslt == 1 )
		return TRUE;
	return FALSE;
}

/* Entry point which finds signer from sinfo->by */
	static PGPBoolean
mntSigOKWithRegexp( PGPKeyDBObj const *sig )
{
	PGPKeyDBObj *signer;
	PGPSigInfo *sinfo;

	pgpAssert( OBJISSIG( sig ) );

	/* See if signing key got its trust conditioned with a regexp */
	sinfo = pgpSigToSigInfo( sig );
	signer = sinfo->by;
	return mntSigOKWithRegexpOnSigner( sig, signer );
}



/******************** Signature Utility Functions **********************/


/*
 * Check to see if the signature is valid at this point in time.  
 *
 * To avoid overflow problems with 65535 days being larger than a 32-bit
 * timestamp, compute how old the signature is in days, and compare
 * that with the validity period.  If its age, in days rounded down,
 * is < the validity period, it is valid.  To deal with a validity
 * period of 0 being infinite, subtract one from the validity using
 * unsigned arithmetic and change the < to <=.  (n < 5 iff n <= 4, for
 * integer n).  0 will wrap to UINT_MAX, and every unsigned number
 * compared <= UINT_MAX, so the test will always be true.
 *
 */
static PGPBoolean
mntSigIsValidTime(PGPUInt32 timenow, PGPUInt32 tstamp, PGPUInt32 validity)
{
	/* For dates in future, give 24 hour slop */
	if( timenow < tstamp )
		return  timenow + 24*3600 > tstamp;
	/* Else check for expiration */
	return (PGPUInt32)(timenow-tstamp) <= (validity-1u) ;
}

/* True if signature is a valid, checked, unexpired key signature. */
static PGPBoolean
mntSigIsValidTimeKeySig(PGPKeyDBObj const *sig, PGPUInt32 timenow)
{
	PGPSigInfo *sinfo;

	if( !OBJISSIG( sig ) )
		return FALSE;
	if( !pgpKeyDBObjIsReal( sig ) )
		return FALSE;
	sinfo = pgpSigToSigInfo( sig );
	return
		   (sinfo->trust & PGP_SIGTRUSTF_CHECKED)
		&& !(sinfo->trust & PGP_SIGTRUSTF_REVOKEDBYCRL)
		&& (sinfo->type & 0xF0) == PGP_SIGTYPE_KEY_GENERIC
		&& mntSigOKWithRegexp( sig )
		&& mntSigIsValidTime(timenow, sinfo->tstamp, sinfo->sigvalidity);
}
		
/*
 * Check if the sig is valid, that is, not expired, not in the future,
 * cryptographically checked, not revoked by CRL, and OK with regexp.
 */
static PGPBoolean
mntSigIsValid( PGPKeyDBObj const *sig, PGPUInt32 timenow)
{
	PGPSigInfo *sinfo;

	pgpAssert(OBJISSIG(sig));
	sinfo = pgpSigToSigInfo( sig );
	return (sinfo->trust & PGP_SIGTRUSTF_CHECKED)
		&& !(sinfo->trust & PGP_SIGTRUSTF_REVOKEDBYCRL)
		&& mntSigOKWithRegexp( sig )
		&& mntSigIsValidTime( timenow, sinfo->tstamp, sinfo->sigvalidity );
}

/*
 * Return the newest sibling signature, based on the nextby fields.
 * Advances *sig to point beyond the sigs on this object
 * Sig must be cryptographically valie, but it may be expired or revoked.
 */
static PGPKeyDBObj *
mntNewestSiblingSig(PGPKeyDBObj const **sig)
{
	PGPKeyDBObj const *newest;
	PGPSigInfo *siginfo;
	PGPSigInfo *newsiginfo;

	pgpAssert(OBJISSIG(*sig));
	siginfo = pgpSigToSigInfo( *sig );
	newest = (*sig);
	newsiginfo = siginfo;
	while ((*sig = siginfo->nextby) != NULL) {
		pgpAssert(OBJISSIG(*sig));
		siginfo = pgpSigToSigInfo( *sig );
		if( !pgpKeyDBObjIsReal( *sig ) )
			continue;
		if( (*sig)->up != newest->up )
			break;
		if( siginfo->trust & PGP_SIGTRUSTF_CHECKED
				&& newsiginfo->tstamp < siginfo->tstamp )
		{
			newest = (*sig);
			newsiginfo = siginfo;
		}
	}
	return (PGPKeyDBObj *)newest;
}


/* True if a non-exportable sig for which we don't have the secret */
static PGPBoolean
mntForeignSignature(PGPKeyDBObj const *sig)
{
	PGPKeyDBObj *key;
	PGPSigInfo *sinfo;
	PGPKeyInfo *kinfo;

	pgpAssert( OBJISSIG( sig ) );
	sinfo = pgpSigToSigInfo( sig );

	/* False if exportable */
	if( SIGISEXPORTABLE(sinfo) )
		return FALSE;

	key = sinfo->by;
	pgpAssert( pgpKeyDBObjIsReal( key ) );
	pgpAssert( OBJISKEY( key ) );
	kinfo = pgpKeyToKeyInfo( key );
	
	/* False if by axiomatic key */
	if( kinfo->trust & PGP_KEYTRUSTF_BUCKSTOP )
		return FALSE;
	/* Or if by a secret key */
	if( pgpKeyIsSec( key ) )
		return FALSE;
	/* Else true, a non-exportable sig by a non-secret key */
	return TRUE;
}	



/********************** Trust Model 2 ***************************/

#define LOOKINGAT(key) (((key)->flags & KEYF_TRUSTTMP) != 0)
#define SETLOOKINGAT(key) ((key)->flags |= KEYF_TRUSTTMP)
#define CLEARLOOKINGAT(key) ((key)->flags &= ~KEYF_TRUSTTMP)

/*
 * Maximum number of paths we will keep.
 * Must calculate trust for each subset.
 */
#define TOTALPATHMAX 10


/*
 * The Path and PathList routines use a convention copied from the
 * PGPPipeline package for tail pointers.  The tail pointer points
 * at the "next" pointer of the last packet, or if there are no packets
 * it points at the "head" pointer for the whole list.  This allows a
 * uniform interface for adding packets whether they are the first or
 * not.
 */

#undef DEBUGPATH

#ifdef DEBUGPATH

static char const hexchar[16] = {
	'0','1','2','3','4','5','6','7',
	'8','9','A','B','C','D','E','F'
};

static int
pgpDebugPrintKeyID(FILE *f, PGPKeyDBObj *key)
{
	PGPKeyInfo *kinfo;
	PGPByte *buf;
	int i;

	pgpAssert (OBJISKEY(key));
	kinfo = pgpKeyToKeyInfo( key );
	buf = kinfo->keyID;
	for (i = 4; i < 8; i++) {
		putc(hexchar[buf[i] >> 4 & 15], f);
		putc(hexchar[buf[i] & 15], f);
	}
	return 8;
}

static int
pgpDebugPrintKeyUserID(FILE *f, PGPKeyDBObj *key)
{
	char buserid[256];
	PGPByte const *udata;
	PGPKeyDBObj *uid;
	size_t len, hlen;

	uid = key->down;
	while (IsntNull(uid) && !OBJISUSERID(uid)) {