pgprngmnt.c

来自「著名的加密软件的应用于电子邮件中」· C语言 代码 · 共 2,034 行 · 第 1/5 页

/*
* Add "inc" trust to the name signed by the given sig.
* If the trust passes "thresh", mark the name with the level
* and add the key that owns it to the list. Return the expanded list.
*
* TODO: Do something sensible with signatures on keys.
*/
static struct RingKey const *
mntDoSig(struct RingSig const *sig, struct RingKey const *list,
	int const inc, int const thresh, word32 const timenow, int const level)
{
	union RingObject *name, *key;
	byte sigtype;

	(void)timenow;	/* Avoid warning */
	pgpAssert(mntSigIsValid(timenow, sig->tstamp, sig->validity));

	name = sig->up;
	if (!OBJISNAME(name)) {
		/* @@@ do anything with sigs on keys? */
		return list;
	}

#if 0
	/* Ignore self-signature */
	key = name->n.up;
	pgpAssert(OBJISKEY(key));
	if (key == sig->by)
	return list;
#endif

	sigtype = sig->type & 0xF0;
	if (sigtype != PGP_SIGTYPE_KEY_GENERIC)
		return list;

#if PRINT_PROGRESS
	printf("  Trust %d/%d -> %d/%d on name ",
	name->n.trustval, thresh,
	name->trustval + inc, thresh);
	(void)ringTtyPutString(name->name, name->len, -1u, stdout, '"', '"');
	putchar('\n');
#endif
	name->n.trustval += inc;
	/*
	* If we are not yet at the valid level or have already
	* marked this name as validated, bail out.
	*/
	if (name->n.trustval < thresh || NAMELEVEL(&name->n))
		return list;
	/* Passed threshold - label with certification level. */
	NAMESETLEVEL(&name->n, level);
	key = name->n.up;
	pgpAssert(OBJISKEY(key));
	if (key->g.flags & KEYF_TRUSTED ||	/* Already listed? */
	key->k.trust & (PGP_KEYTRUSTF_REVOKED | PGP_KEYTRUSTF_EXPIRED))
		return list;
#if PRINT_PROGRESS
	ringKeyIDprint(stdout,
"    Potential introducer: first userID trust >= 1 on keyID ",
		 	key->keyID);
#endif
	key->k.util = (struct RingKey *)list;
	key->g.flags |= KEYF_TRUSTED;
	return &key->k;
}


/*
* Look for other keys signed by the grandparent of sig which have the same
* name. Propagate the same trust to those names. (Don't do it if they
* have a sig by the same signing key.) The reasoning is that the same
* person owns both keys, he has the same name, so sigs on the first name
* can be treated as though they are on the other name. This will facilitate
* moving to a new key from an old one.
*
* One issue not dealt with here is that if the grandparent key here is also
* a trusted introducer, trust will move to the destination key in two ways:
* here, by direct "pair propagation" from signatures on that key's names
* which match the names here; and also by normal trust propagation due to
* the signature. This could end up counting some trust twice, although
* in this trust model it doesn't look like it introduces any significant
* weaknesses.
*/

static struct RingKey const *
mntDoMatchingNames(struct RingSig const *sig, struct RingKey const *list,
	RingSet const *set, int const inc, int const thresh, word32 const timenow,
	int const level)
{
	RingObject			*name;		/* Name which sig is on */
	RingObject			*key;	 	/* Key which name is on */
	RingObject			*propsig;	 /* All sigs by key */
	RingObject			*propname;	/* Name which propsig is on */
	RingObject			*propkey;	 /* Key which propname is on */
	RingObject			*namesig;	 /* All sigs on propname */
	byte				sigtype;
	byte				selfsigfound;
	ringmask const		mask = set->mask;

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

	/* Ignore sigs not on names */
	name = sig->up;
	if (!OBJISNAME(name))
		return list;

	/* Ignore self signatures, invalid keys, and keys which don't sign */
	key = name->n.up;
	pgpAssert(OBJISKEY(key));
	if (key == sig->by)
	return list;
	if (key->k.trust & (PGP_KEYTRUSTF_REVOKED | PGP_KEYTRUSTF_EXPIRED))
		return list;

	/* Ignore funny kinds of sigantures */
	sigtype = sig->type & 0xF0;
	if (sigtype != PGP_SIGTYPE_KEY_GENERIC)
		return list;

	/*
	* As a short-term security precaution, only propagate for fully valid
	* names. The problem is that otherwise, someone could have two keys,
	* A and B, which both are marginally valid.  If both A and B sign key
	* C which has the same name, the marginally valid signatures combine
	* to give full validity to C. We have a solution to this but it is
	* complex. For now we will only do propagation from names which are
	* fully valid, which will mean that only fully valid keys get their
	* trust propagated to matching names.
		*/
	if (!NAMELEVEL(&name->n))
		return list;

	/* Look for other keys with same name */
	for (propsig = key->k.sigsby; propsig;
						propsig = (RingObject *)propsig->s.nextby) {
		if (!(propsig->g.mask & mask))
			continue;
		propname = propsig->s.up;

		/* Ignore sigs not on names */
		if (!OBJISNAME(propname))
			continue;
		propkey = propname->n.up;

		/* Ignore nonkeys(?) or self sigs */
		if (!OBJISKEY(propkey) || propkey == key)
			continue;

		/* Make sure signature is valid */
		if (!(propsig->s.trust & PGP_SIGTRUSTF_CHECKED)
		|| !(propsig->s.mask & mask)
		|| !mntSigIsValid(timenow, propsig->s.tstamp, propsig->s.validity))
			continue;
		if ((propsig->s.type & 0xF0) != PGP_SIGTYPE_KEY_GENERIC)
			continue;

		/* See if names match */
		if (ringNamesDiffer (set, name, propname))
			continue;

		/* Skip if name already has a sig from our signer */
		/* Also, this must be the newest sig by us */
		/* Also, it must have a self signature */
		selfsigfound = 0;
		for (namesig=propname->n.down; namesig; namesig=namesig->s.next) {
			if (!OBJISSIG(namesig) || !(namesig->g.mask & mask))
				continue;
			if (namesig->s.by == sig->by)
				break;		/* Break out with nonnull namesig on match */
			if (namesig != propsig && namesig->s.by == key
						&& namesig->s.tstamp >= propsig->s.tstamp)
				break;		/* Break outwith nonnull namesig if not newest */
			/* Check for valid self signature */
			if (namesig->s.by == propkey
				&& (namesig->s.trust & PGP_SIGTRUSTF_CHECKED)
				&& (namesig->s.mask & mask)
				&& mntSigIsValid(timenow, namesig->s.tstamp,
												namesig->s.validity)) {
				selfsigfound = 1;
			}
		}

		/* If namesig is non-null it had a matching sig, skip this name */
		/* Also if there was no self signature */
		if (namesig || !selfsigfound)
			continue;

		/* OK, we have a name suitable for propagating trust to */
		list = mntDoSig(&propsig->s, list, inc, thresh, timenow, level);
	}
	return list;
}


/*
* Add "inc" trust 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 struct RingKey const *
mntWalkSigList(struct RingSig const *sigs, struct RingKey const *list,
	RingSet const *set, int const inc, int const thresh, word32 const timenow,
	int const level)
{
	struct RingSig const *cur;
	ringmask const mask = set->mask;

	while (sigs) {
		/* Find the first valid checked signature under the mask. */
		if (!(sigs->trust & PGP_SIGTRUSTF_CHECKED)
		|| !(sigs->mask & mask)
		|| !mntSigIsValid(timenow, sigs->tstamp, sigs->validity))
		{
			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
			*/
		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, under the right mask, and
			* more recent than cur.
			 		*
			 		*/
			if (sigs->trust & PGP_SIGTRUSTF_CHECKED
			&& sigs->mask & mask
			&& cur->tstamp < sigs->tstamp
			&& mntSigIsValid(timenow, sigs->tstamp,
					sigs->validity))
				cur = sigs;
		}

		/* Do the trust computations on the resultant signature. */
		list = mntDoSig(cur, list, inc, thresh, timenow, level);

		/* Propagate sig info also to linked keys with matching names */
		list = mntDoMatchingNames(cur, list, set, inc, thresh, timenow, level);

	}
	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 struct RingKey const *
mntList(struct RingKey const *list, RingSet const *set, int const add[8],
	int const threshold, word32 const timenow, unsigned const level)
{
	struct RingKey const *newlist;
	int trustinc;

	for (newlist = 0; list; list = list->util) {
		pgpAssert(list->flags & KEYF_TRUSTED);
		trustinc = add[list->trust & PGP_KEYTRUST_MASK];
#if PRINT_PROGRESS
		printf(, "Adding %d/%d trust from ", trustinc, threshold);
		ringKeyPrint(stdout, (struct 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)
			continue;
		newlist = mntWalkSigList(&list->sigsby->s, newlist, set, trustinc,
		threshold, timenow, level);
	}

	return newlist;
}

#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 word16
mergetrust(word16 t1, word16 t2)
{
	static double const k = -M_LN10 / PGP_TRUST_DECADE;
	double p, q;

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

	/* Round down for conservative estimate */
	return (word16)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 word16
calctrust(struct RingKey const *k, ringmask mask)
{
	union RingObject const *n;
	word16 cur, best = 0;
#if BESTVALID
	word16 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;