pgprngmnt.c

vc环境下的pgp源码

 * Walk a list of keys (linked through the util field), adding the
 * appropriate trust values to the names the key has signed.
 */
static RingKey const *
mntList(RingKey const *list, RingSet const *set, int const add[8],
	int const threshold, PGPUInt32 const timenow, unsigned const level)
{
	RingKey const *newlist;
	int trustinc;				/* Trust from trust packets */
	int signedtrustinc;			/* Trust from signatures */

	for (newlist = 0; list; list = list->util) {
		pgpAssert(list->flags & KEYF_TRUSTED);
		trustinc = add[list->trust & kPGPKeyTrust_Mask];
		signedtrustinc = add[list->signedTrust & kPGPKeyTrust_Mask];
#if PRINT_PROGRESS
		printf(, "Adding %d/%d trust from ", trustinc, threshold);
		ringKeyPrint(stdout, (RingPool *)0, "", list);
#endif
#if 0
		/*
		 * @@@ PGP 2.x allows disabled keys to participate in
		 * trust computation.  Should this be added?
		 */
		if (list->trust & (PGP_KEYTRUSTF_DISABLED))
			continue;
#endif
		if (trustinc <= 0 && signedtrustinc <= 0)
			continue;
		newlist = mntWalkSigList(&list->sigsby->s, newlist, set, trustinc,
		                         signedtrustinc, threshold, timenow, level);
	}

	return newlist;
}


/******************** Trust Model 1&2 Helpers *************************/

#else /* PGPTRUSTMODEL>0 */

/*
 * This finds the combined trust value given two trusts which
 * are arranged in series.  Trust values are actually the
 * scaled negative logarithms of *distrust*, so assuming
 * independent failures, two signatures in parallel have a
 * distrust which is the product of the input distrusts, and
 * we only have to add the trust values.  But when they're
 * in series, we want to multiply the *trusts*, and it gets hairier...
 * This is a quick and dirty brute-force-and-ignorance approach.
 * I know of better solutions, but haven't had time to do the
 * necessary numerical analysis.
 *
 * @@@ Optimize this code
 *
 * Given t1 = log(p1)/k and t2 = log(p2)/k, where p1 and p2 are
 * probabilities that are bounded between 0 < p1,p2 <= 1, find
 * t3 = log(1-(1-p1)*(1-p2))/k
 *    = log(1-(1-exp(t1*k))*(1-exp(t2*k)))/k.
 *    = log(p1 + p2 - p1*p2)
 *    = log(exp(t1*k) + exp(t2*k) - exp(t1*k)*exp(t2*k))/k
 * k is chosen to make the logs come out right,
 * so that an increment of TRUST_DECADE corresponds to 1/10.
 * I.e. exp(TRUST_DECADE*k) = 1/10
 *   =>      TRUST_DECADE*k = log(1/10)
 *   =>                   k = -log(10)/TRUST_DECADE;
 * Well, actually there's an additional factor of TRUST_CERTSHIFT
 * thrown in there, a factor of 64 which allows probabilities down to
 * 10^-25 and a granularity of +/-0.09% in trust values.
 * Note that p1+p2-p1*p2 = p1 + p2*(1-p1) >= p1, so the output
 * probability is always greater than either of the input probabilities,
 * so t3 is always less than t1 or t2.  Thus, the computation can't
 * overflow.
 *
 * I'd prefer to somehow evaluate it directly in log form, using
 * something like Zech's log function to evaluate it.
 * H'm... an alternate evaluation technique...
 *   p1 * (1 + p2/p1(1-p1))
 * = p1 * (1 + p2*(1/p1-1))
 * Choose p1 as the larger of the two... does this lead to anything?
 * Yes.  Two tables of size 771 (= ceil(log(2)*40*64)) will allow you
 * to evaluate (1/p1-1) directly, guaranteed to round down, and then
 * I think something similar will do for (t+1).  For the (1/p1-1)
 * evaluation, do the entries for p1 from 1 to 1/2 directly, and
 * past that, the value of (1/p1-1) differes from the value of
 * 1/p1 by at most 771.  Record in another table the values at
 * which the delta changes, do a binary search, and use the index as
 * the delta.
 */
#include <math.h>
#ifndef M_LN10
#define M_LN10	2.30258509299404568402	/* ln(10) */
#endif
static PGPUInt16
mergetrust(PGPUInt16 t1, PGPUInt16 t2)
{
	static double const k = -M_LN10 / PGP_TRUST_DECADE;
	double p, q;

	/* Saturate at infinity */
	if (t1 == (PGPUInt16) PGP_TRUST_INFINITE)
		return t2;
	if (t2 == (PGPUInt16) PGP_TRUST_INFINITE)
		return t1;
	p = exp(t1*k);
	q = exp(t2*k);

	/* Round down for conservative estimate */
	return (PGPUInt16)floor(log(p + q - p*q)/k);
}

/*
 * Compute the trust value associated with a key.  This is the
 * weight given to signatures made by that key.  The decision is based
 * on the validity of the key's name (how sure are we that the name
 * belongs to that key) and confidence (how much do we trust the
 * named individual).  The product of those two gives the trust in
 * the key as a whole.
 *
 * If the key is a buckstop key, ignore the validity and just take the
 * confidence as-is.
 *
 * If there are multiple names on a key, compute the trust for each and
 * use the maximum.
 *
 * BESTVALID alternate algorithm
 *
 * If BESTVALID if set, then the overall trust in a key is determined
 * from the name with the highest validity.  In the case of a tie,
 * then the best validity*confidence is taken.  Thus, overall trust
 * is computed from the name this key is most likely to belong to.
 */
#ifndef BESTVALID
#define BESTVALID 1
#endif

static PGPUInt16
calctrust(RingKey const *k, RingSet const *set)
{
	union RingObject const *n;
	PGPUInt16 cur, best = 0;
#if BESTVALID
	PGPUInt16 bestvalid = 0;
#endif

	pgpAssert(KEYISKEY(k));

	/* For BUCKSTOP keys, validity and confidence are infinite.
	   Revoked or expired keys have no validity or confidence. */
	if (k->trust & (PGP_KEYTRUSTF_REVOKED | PGP_KEYTRUSTF_EXPIRED))
		return 0;
	if (k->trust & PGP_KEYTRUSTF_BUCKSTOP)
		return PGP_TRUST_INFINITE;

	for (n = k->down; n; n = n->g.next) {
#if BESTVALID
		if (OBJISNAME(n) && pgpIsRingSetMember(set, n) && 
		    n->n.valid >= bestvalid)
#else
		if (OBJISNAME(n) && pgpIsRingSetMember(set, n))
#endif
		{
			cur = n->n.confidence;
			if (cur == PGP_NEWTRUST_INFINITE)
				cur = n->n.valid;
			else if (cur == PGP_NEWTRUST_UNDEFINED)
				cur = 0;
			else
				cur = mergetrust((PGPUInt16)(cur << TRUST_CERTSHIFT),
				                 n->n.valid);
#if BESTVALID
			if (n->n.valid > bestvalid ||
			    (n->n.valid == bestvalid && cur > best)) {
			         best = cur;
				 bestvalid = n->n.valid;
			}
#else
			if (cur > best)
				best = cur;
#endif
		}
	}
	return best;
}

PGPUInt16 
ringKeyCalcTrust(RingSet const *set, union RingObject *key)
{
	PGPUInt16 trust;
	double confidence;
	pgpAssert(OBJISKEY(key));
	pgpAssert(pgpIsRingSetMember(set, key));
#if PGPTRUSTMODEL==2
	confidence = pathKeyConfidence (key, set);
	if (confidence >= 1.)
		trust = PGP_TRUST_INFINITE;
	else
		trust = ringDoubleToTrust (1. / (1.-confidence));
#else
	(void) confidence;
	trust = calctrust (&key->k, set);
#endif
	return trust;
}
	       
#endif /* PGPTRUSTMODEL>0 */


/********************** Trust Model 1 ***************************/

#if PGPTRUSTMODEL==1

/*
 * Add confidence to the name signed by the given sig, and if the name
 * has confidence and the key has not already been processed, add it
 * to the list.  Return the expanded list.
 *
 * TODO: Do something sensible with signatures on keys.
 */
static RingKey *
mntDoSig(RingSig const *sig, RingKey *list,
	PGPUInt16 confidence, PGPUInt32 const timenow, int const level,
	int pass2)
{
	union RingObject *name, *key;
	int i;
	PGPByte sigtype;

	pgpAssert(mntSigIsValid(timenow, sig->tstamp, sig->sigvalidity));

	/* Okay, it hasn't expired, check that we have a name signature */
	name = sig->up;

	if (!OBJISNAME(name)) {
		/* @@@ Do anything here with signatures on keys? */
		return list;
	}

	sigtype = sig->type & 0xF0;
	if (sigtype != PGP_SIGTYPE_KEY_GENERIC)
		return list;
	key = name->n.up;
	pgpAssert(OBJISKEY(key));
	/* Do not add confidence from a key to itself */
	if (key == sig->by)
		return list;
	/*
	 * There are two passes: first we add trust from keys at one level
	 * to keys on the next level, then we add trust from keys at
	 * that level to each other.  Pass2 is a flag controlling which
	 * we do.
	 * Oh, names which we have no confidence in as introducers
	 * get their certainty added from all levels, since they cannot
	 * participate in cycles.  This is done during pass 1.
	 * So, during pass 1:
	 * - Ignore names on keys that we have already recorded that are
	 *   at levels less than the current one.
	 * And during pass 2:
	 * - Ignore names other than ones at the specified level on keys
	 *   that *are* trusted.  (On keys that are not will get added
	 *   next iteration).
	 */
	i = NAMELEVEL(&name->n);
	if (!pass2) {
		/* Pass 1 */
		if (!i)
			NAMESETLEVEL(&name->n, level);
		else if (i < level && key->g.flags & KEYF_TRUSTED)
			return list;
	} else {
		/* Pass 2 */
		if (i != level || !(key->g.flags & KEYF_TRUSTED))
			return list;
	}

	/* Okay, now add the confidence if needed.  Do special
	   checks for infinite confidence and validity.  */

	if (confidence == PGP_TRUST_INFINITE)
		name->n.valid = PGP_TRUST_INFINITE;
	else if (name->n.valid != PGP_TRUST_INFINITE) {
		name->n.valid += confidence;
		/*
		 * Saturate on overflow.  65535 is reserved for "perfect".
		 * 65534 is 2.5164 * 10^-26, 2^-85.  
		 */
		if (name->n.valid + 1 <= confidence)
			name->n.valid = (PGPUInt16) PGP_TRUST_MAX; 
	}

	/*
	 * Don't add keys to the list if:
	 * - Already on list
	 * - Key is revoked (confidence is zero then)
	 * - Key is expired (same as revoked)
	 * - Name has no confidence
	 * Currently, disabled keys *are* allowed on the list,
	 * to participate in trust transactions.  Disabling only
 	 * affects key selection.  This is PGP 2.x compatible.
	 *
	 * Once a key is on the list, only one more round of adding
	 * certainty to its names is possible, since two rounds could
	 * create cycles that correcting for is difficult.  Thus,
	 * we want to avoid putting things on the list unnecessarily,
	 * but prefer to weed out everything possible now.
	 */
	if (key->g.flags & KEYF_TRUSTED	/* Already listed? */
	    || key->k.trust & (PGP_KEYTRUSTF_REVOKED | PGP_KEYTRUSTF_EXPIRED)
/*	    || key->k.trust & PGP_KEYTRUSTF_DISABLED */ /*PGP 2.x compatible*/
	    || !name->n.confidence)
		return list;
	key->k.util = (RingKey *)list;
	key->g.flags |= KEYF_TRUSTED;
	return &key->k;
}

/*
 * Add confidence to each name signed by a valid signature on
 * the "sigs" list.  If the trust passes "thresh", add the resultant
 * key to the list.  Return the expanded list.
 *
 * Signatures that are expired or have been superseded are weeded out.
 * Note that a postdated signature does not supersede one dated yesterday!
 */
static RingKey *
mntWalkSigList(RingSig const *sigs, RingKey *list,
	PGPUInt16 confidence, RingSet const *set, PGPUInt32 const timenow,
	int const level, int pass2)
{
	RingSig const *cur;

	while (sigs) {
		/* Find the first valid checked signature in the set. */
		if (!(sigs->trust & PGP_SIGTRUSTF_CHECKED)
			|| (sigs->trust & PGP_SIGTRUSTF_REVOKEDBYCRL)
			|| !pgpIsRingSetMember(set, (RingObject *)sigs)
		    || !mntSigIsValid(timenow, sigs->tstamp, sigs->sigvalidity))
		{
			sigs = sigs->nextby;
			continue;
		}
		/* The first candidate signature */
		cur = sigs;

		/*
		 * Search all other signatures by this key on the same object
		 * for the most recent valid signature, which is the only
		 * one which is accorded any weight.  We use the fact that
		 * after ringPoolListSigsBy places all signatures on
		 * the same object together in the sigsby list.
		 */
		while ((sigs = sigs->nextby) != NULL && sigs->up == cur->up)
		{
			/*
			 * So now that the signature at the front of the sigs
			 * list is on the same thing as "cusrig", consider
			 * replacing cur, if the new signature is is
			 * checked good, valid, in the set, and
			 * more recent than cur.
			 * 
			 */
			if (sigs->trust & PGP_SIGTRUSTF_CHECKED
				&& !(sigs->trust & PGP_SIGTRUSTF_REVOKEDBYCRL)
				&& pgpIsRingSetMember(set, (RingObject *)sigs)
			    && cur->tstamp < sigs->tstamp
			    && mntSigIsValid(timenow, sigs->tstamp,
			                     sigs->sigvalidity))
				cur = sigs;
		}

		/* Do the trust computations on the resultant signature. */
		list = mntDoSig(cur, list, confidence, timenow, level, pass2);
	}
	return list;
}

/*
 * Walk a list of keys (linked through the util field), adding the
 * appropriate trust values to the names the key has signed.
 */
static RingKey const *
mntList(RingKey const *list, RingSet const *set,
	PGPUInt32 const timenow, unsigned const level)
{
	RingKey *newlist;
	RingKey *cur;
	PGPUInt16 confidence;

	/* Do first pass, adding trust from old list to new things */
	for (newlist = NULL; list; list = list->util) {
		pgpAssert(list->flags & KEYF_TRUSTED);
		confidence = calctrust(list, set);
		if (!confidence)
			continue;
		newlist = mntWalkSigList(&list->sigsby->s, newlist, confidence,
		                         set, timenow, level, 0);
	}
	/*
	 * Do second pass, adding trust from new list to itself.
	 * The overall confidence for each key must be calculate