pgprngmnt.c

vc环境下的pgp源码

/*
 * pgpRngMnt.c - Perform the maintenance pass over a keyring.
 * This is a lot more efficient that the way PGP 2.x did it and,
 * I modestly think, easier to understand to boot.
 *
 * Written by Colin Plumb
 *
 * $Id: pgpRngMnt.c,v 1.74.6.1 1999/06/04 00:28:50 heller Exp $
 */
#include "pgpConfig.h"

#include <string.h>	/* For strlen() */
#include <time.h>
#include <stddef.h>

#include "pgpDebug.h"
#include "pgpMakeSig.h"
#include "pgpMem.h"
#include "pgpPktByte.h"
#include "pgpRegExp.h"
#include "pgpRngMnt.h"
#include "pgpRngPars.h"
#include "pgpRngPriv.h"
#include "pgpRngPkt.h"
#include "pgpRngRead.h"
#include "pgpTrust.h"
#include "pgpTrstPkt.h"
#include "pgpTimeDate.h"
#include "pgpHashPriv.h"
#include "pgpErrors.h"
#include "pgpPubKey.h"
#include "pgpRngRead.h"	/* for ringFetchObject */
#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 old trust model (PGPTRUSTMODEL==0) --
 *
 * Each key has an introducer trust, either ultimate, complete, or
 * partial.  These have scores of 1, 1/x and 1/y.  For each key on the
 * axiomatically trusted list, and each signature made by that key on
 * a name, the introducer trust is added to the name's validity score.
 * If that score reaches 1, the name's key is added to the next introducer
 * list and its introducer trust is used for the level after that.
 *
 * At the end, names are graded according to their score.
 * If it is >= 1, they are completely valid.  If it is >= 1/2,
 * they are partially valid.  If < 1/2, they are not valid at all.
 * Partial versus lack of validity only affects the warning messages
 * printed out.  If a key does not have any comletely valid names,
 * its introducer trust is set to 0.
 *
 * There are actually three kinds of zero introducer trust:
 * - Undefined, meaning that it has not been set.  If a key has
 *   a completely valid name and undefined introducer trust, the
 *   user is asked to set one.
 * - Unknown
 * - Untrusted
 *   These latter two are equivalent valid "set" values, with the
 *   only difference being for user-interface purposes.
 *
 *
 * -- The new trust model (PGPTRUSTMODEL == 1 or 2) --
 *
 * 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 name, it is correct.
 * Add up the probabilities of all the cases in which the name is correct,
 * and you have the computed probability that the name is correct.
 *
 * For PGPTRUSTMODEL==1:
 *
 * Basically, you have to consider every possible path from the root
 * set of axiomatically trusted keys to the name in question and correct
 * for overlaps and loops.  This can't be done in a reasonable amount of
 * time, but a conservative approximation can be made.  By leaving out
 * some of the more complex paths, a lower probability can be computed.
 * Since it is lower than the ideal computation, it can still be trusted.
 * A good approximation is fast to compute and yet approaches the ideal
 * approximation well.
 *
 * Since PGP supports multiple names on a key, the question arises
 * which validity value is used.  The solution here is to assign a trust
 * value to each of the names, take the validity*trust product for each
 * name, and take the maximum.  A name which is meaningless to the user
 * (e.g. a name in an unknown character set, such as cyrillic or kanji)
 * can't be trusted, but that doesn't mean that a second name which *is*
 * intelligible should be penalized.
 *
 * The approximation that PGP uses is as follows:
 * - Clear all trust accumulators to 0.
 * - Starting with a root set of keys (level 0), each of which have some
 *   specified confidence, take that confidence directly as the trust.
 *   This is currently assumed to be ultimate.  For each signature made
 *   by such a key, add the confidence to the name's valididty score.
 * - Using this provisional validity, multiply each names's confidence
 *   by its validity to get a provisional trust.  Use this trust to
 *   increase the validity score of each name already processed.
 * - Multiply the final validity by the confidence to get the final trust
 *   on the key, which is used
 *
 * Description of PGPTRUSTMODEL==2:
 *
 * 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.
 * - Use a ringset composed only of trusted introducers and the target 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 name(s) on a key.  This means that the output of the
 * calculation above is a validity value for a particular name on a
 * key, based on the signatures on that name.  The inputs need to be
 * based on the user defined confidence values for the names.  The
 * complication arises for keys which have more than one name (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 name, the confidence of that name is used.
 * If there is more than one name, a conservative approach is to use
 * the name with the smallest user-defined confidence value.  (Names
 * for which the user has not specified a confidence level do not
 * enter into this calculation.)  If all of the names (of those with
 * non-zero confidence) have validity values (from earlier runs of the
 * trust calculation) then we can choose the confidence of the name
 * with the highest validity as in PGPTRUSTMODEL==1.
 *
 * Not all of the optimizations above are implemented in the current
 * code, nor has it been thoroughly tested.  In particular, the
 * ringMnt 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.)
 */




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


/* Clear key regexp pointers */
	static void
mntClearKeyRegexps( RingSet const *set )
{
	RingPool *pool = set->pool;
	RingObject *key;

	for (key=pool->keys; key; key=key->g.next) {
		if (!pgpIsRingSetMember(set, key))
			continue;
		key->k.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 int
mntSigOKWithRegexp( RingSet const *set, RingSig const *sig )
{
	RingObject *parent;
	RingObject *signer;
	char const *sname;
	PGPSize len;
	int rslt;

	/* See if signing key got its trust conditioned with a regexp */
	signer = sig->by;
	if (!signer->k.regexp)
		return TRUE;

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

	/* See if name matches regexp */
	sname = ringNameName (set, parent, &len);
	rslt = pgpRegExec( (regexp *)signer->k.regexp, sname );
	if (rslt == 1)
		return TRUE;
	return FALSE;
}



/******************** 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
mntSigIsValid(PGPUInt32 timenow, PGPUInt32 tstamp, PGPUInt32 validity)
{
    return 
	  (timenow <= tstamp || (PGPUInt32)(timenow-tstamp) <= validity-1u);
}

/* True if signature is a valid, checked, unexpired key signature.  If
 * set is non-null it also checks that sig is in the set.
 */
static PGPBoolean
mntSigIsValidKeySig(RingObject const *sig, RingSet const *set,
	PGPUInt32 timenow)
{
	return OBJISSIG(sig)
		&& (sig->s.trust & PGP_SIGTRUSTF_CHECKED)
		&& !(sig->s.trust & PGP_SIGTRUSTF_REVOKEDBYCRL)
		&& (IsNull(set) || pgpIsRingSetMember(set, sig))
		&& (sig->s.type & 0xF0) == PGP_SIGTYPE_KEY_GENERIC
		&& (IsNull(set) || mntSigOKWithRegexp( set, &sig->s ))
		&& mntSigIsValid(timenow, sig->s.tstamp, sig->s.sigvalidity);
}
		

/*
 * Return the newest sibling signature, based on the nextby fields.
 * Advances *sig to point beyond the sigs on this object
 */
static RingSig *
mntNewestValidSiblingSig(RingSig const **sig, RingSet const *set,
	PGPUInt32 timenow)
{
	RingSig *newest;

	pgpAssert(SIGISSIG(*sig));
	newest = (RingSig *)(*sig);
	while ((*sig = (*sig)->nextby) != NULL && (*sig)->up == newest->up) {
		if ((*sig)->trust & PGP_SIGTRUSTF_CHECKED
			&& !((*sig)->trust & PGP_SIGTRUSTF_REVOKEDBYCRL)
			&& pgpIsRingSetMember (set, (RingObject *)(*sig))
			&& newest->tstamp < (*sig)->tstamp
			&& mntSigOKWithRegexp( set, *sig )
			&& mntSigIsValid(timenow, (*sig)->tstamp, (*sig)->sigvalidity))
			newest = (RingSig *)(*sig);
	}
	return newest;
}


/* True if a non-exportable sig for which we don't have the secret */
static PGPBoolean
mntForeignSignature(RingSig const *sig, RingSet const *set)
{
	RingObject *key = sig->by;
	RingObject *sec;

	/* False if exportable */
	if (SIGISEXPORTABLE(sig))
		return FALSE;
	/* False if by axiomatic key */
	if (key->k.trust & PGP_KEYTRUSTF_BUCKSTOP)
		return FALSE;
	sec = key->g.down;
	for (sec=key->g.down; sec; sec=sec->g.next) {
		/* False if by a key for which we have secret object */
		if (OBJISSEC(sec) && pgpIsRingSetMember(set, sec))
			return FALSE;
	}
	/* Else true, a non-exportable sig by a non-secret key */
	return TRUE;
}	



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

#if PGPTRUSTMODEL==2

#define LOOKINGAT(key) ((key)->confidence & 1)
#define SETLOOKINGAT(key) ((key)->confidence |= 1)
#define CLEARLOOKINGAT(key) ((key)->confidence &= ~1)

/*
 * 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] = {