pgprngmnt.c

vc环境下的pgp源码

				ptail = pathUnion (phead, ptail, plist->path, pool);
				oddparity = !oddparity;
			}
			plist = plist->next;
			tmask >>= 1;
		}
		pathconf = pathConfidence (phead);
#ifdef DEBUGPATH
		fprintf (stdout, "%sing %g: ", oddparity?" add":" subb",pathconf);
		ringTtyPrintPath (stdout, phead, pool);
#endif
		if (oddparity)
			conf += pathconf;
		else
 			conf -= pathconf;
		pathFreeAll (phead, pool);
		phead = NULL;
		ptail = &phead;
	}
#ifdef DEBUGPATH
	fprintf (stdout, "Net of %g\n", conf);
#endif
	return conf;
}

/*
 * Find the confidence level to use for the given key.
 * This is difficult in this trust model because we generally don't
 * have validity on the names associated with the key, since there is
 * no well defined (nor arbitrarily imposed) ordering of the graph.
 * The result is that when we do our calculation we may end up with a
 * de facto validity on a key/name that has no relation to the (cached)
 * validity stored on the key.
 *
 * So we have a set of heuristics to choose the confidence associated
 * with some name, to wit:
 *
 * If all the names have at least some validity, we choose the confidence
 * associated with the most valid name.  Otherwise we just choose the
 * lowest confidence of all the names.  The reason for the second case is so
 * that if we have a true name and a false name, but the true name doesn't
 * have validity yet, while the false name has a little tiny bit of validity,
 * we don't want to choose the confidence of the false name, which might be
 * very high.  It might be that the next step in the path will give high
 * validity to the true (but low confidence) name.  We would end up counting
 * this key as both high confidence and high validity, which may be wrong.
 *
 * This heuristic might seem to have the problem that if you get a new name
 * for a trusted
 * key its trust will go away until either the new name gets some validity
 * or you set the confidence level on the new name.  But this does not
 * happen because such names are not included in the confident set.
 *
 * A worse problem is that Snidely could get Nell's name on his key, get
 * some low-confidence signer to sign Nell, and get an even lower conf-
 * idence signer to sign his own.  Then we would use Nell's confidence
 * on Snidely's key, and if there were also a good signer on Snidely's name,
 * which we hadn't run into yet, we would again count Snidely's signatures
 * too highly.
 *
 * So this suggests a safer heuristic which is to take either the lowest
 * confidence, or else perhaps to downgrade the confidence by the
 * validities.  However doing this if all the validities are accurate will
 * end up squaring them.  Maybe we could just downgrade by the relative
 * validities, best to worst...
 *
 * (For now we have an #if below to always use the lowest confidence)
 *
 * An idea suggested by Mark is to base the confidence on the particular
 * name which is the next step in the path.  However this complicates the
 * union operation.
 * Either a path no longer has a well defined confidence, preventing
 * Maurer's algorithm from working, or else we have
 * to define a path as being from name to name, and if a key has two
 * names (different email addresses, say, home and work) we would end up
 * counting its contribution to trust twice.  (This is essentially because
 * the assumption of independence fails spectacularly in this case!)
 *
 * Keep in mind that despite all these difficulties, if there is only one
 * name then there is no problem!  We just use the confidence on that name.
 */
static double
pathKeyConfidence (RingObject *key, RingSet const *set)
{
	RingObject     *name;
	double          minconfidence = 1.0,
	                confidence,
	                errorchance,
					nameconfidence,
					keyconfidence,
	                maxvalidconfidence = 0.;
	PGPUInt16       maxvalidity = 0;
	PGPBoolean		allvalid = TRUE;	/* True if all names have validity */
	PGPBoolean		validname = FALSE;	/* True if at least one valid name */

	for (name = key->g.down; name; name = name->g.next) {
		if (!OBJISNAME(name) || !pgpIsRingSetMember(set, name))
			continue;
		if (name->n.confidence == PGP_NEWTRUST_UNDEFINED)
			continue;
		validname = TRUE;
		errorchance =  ringTrustToDouble (
		                    ringTrustToIntern(name->n.confidence));
		confidence = 1. - 1. / errorchance;
		if (confidence < minconfidence)
			minconfidence = confidence;
		if (!name->n.valid) {
			allvalid = 0;
		} else if (name->n.valid > maxvalidity ||
						(name->n.valid == maxvalidity &&
						 confidence < maxvalidconfidence)) {
			maxvalidity = name->n.valid;
			maxvalidconfidence = confidence;
		}
	}
	/* If called with no valid name, minconfidence is 0 */
	if (!validname)
		minconfidence = 0.;
	/*
	 * If all names have known validity, use the most valid name's confidence.
	 * Else choose the lowest established confidence of any name.
	 */
#if 0
/* Too risky to use this heuristic, just take minimum confidence */
	if (allvalid)
		nameconfidence = maxvalidconfidence;
	else
#endif
		nameconfidence = minconfidence;

	keyconfidence = 0.;
	if (key->k.signedTrust != 0) {
		errorchance =  ringTrustToDouble (
		                    ringTrustToIntern(key->k.signedTrust));
		keyconfidence = 1. - 1. / errorchance;
	}

	return pgpMax (keyconfidence, nameconfidence);
}

/* Prototype */
static PathList **
ringFindPathsKey (RingObject *start, PathList **ppath,
	Path **predh, Path **predt, unsigned depth,
    unsigned maxdepth, RingSet const *confset, RingSet const *allset,
	PGPUInt32 timenow, RingPool *pool);

/* Helper routines for ringFindPathsName */

/* Return the newest valid signature by the given key on the given name */
static RingObject *
ringNewestValidSig (RingObject *name, RingObject *key,
	RingSet const *set, PGPUInt32 timenow)
{
	RingObject		*bestsig = NULL,
					*sig;

	pgpAssert (OBJISNAME(name));
	pgpAssert (OBJISKEY(key));

	for (sig = name->g.down; sig; sig = sig->g.next) {
		if (OBJISSIG(sig)
			&& (sig->s.trust & PGP_SIGTRUSTF_CHECKED)
			&& !(sig->s.trust & PGP_SIGTRUSTF_REVOKEDBYCRL)
			&& pgpIsRingSetMember(set, sig)
			&& sig->s.by == key
			&& mntSigOKWithRegexp( set, &sig->s )
			&& mntSigIsValid(timenow, sig->s.tstamp, sig->s.sigvalidity)) {
			/* Good sig by key, see if it is newer than bestsig */
			if (!bestsig
				|| bestsig->s.tstamp < sig->s.tstamp) {
				bestsig = sig;
			}
		}
	}
	return bestsig;
}

/*
 * Return true if there is a signature by the key on an earlier sibling
 * of this name.  This alerts us to a condition which could cause duplicate
 * paths, which will waste resources.
 */
static int
ringEarlierValidSig (RingObject *name, RingObject *key, RingSet const *set,
	PGPUInt32 timenow)
{
	RingObject		*parent,
					*sibname,
					*sig;

	pgpAssert (OBJISNAME(name));
	pgpAssert (OBJISKEY(key));

	parent = name->g.up;
	pgpAssert (OBJISKEY(parent));

	for (sibname=parent->g.down; sibname!=name; sibname=sibname->g.next) {
		if (!OBJISNAME(sibname)
			|| !pgpIsRingSetMember(set, sibname))
			continue;
		for (sig=sibname->g.down; sig; sig=sig->g.next) {
			if (OBJISSIG(sig)
			&& (sig->s.trust & PGP_SIGTRUSTF_CHECKED)
			&& !(sig->s.trust & PGP_SIGTRUSTF_REVOKEDBYCRL)
			&& pgpIsRingSetMember(set, sig)
			&& sig->s.by == key
			&& mntSigOKWithRegexp( set, &sig->s )
			&& mntSigIsValid(timenow, sig->s.tstamp, sig->s.sigvalidity)) {
				/* Have an earlier signature we are looking for */
				return TRUE;
			}
		}
	}
	return FALSE;
}

/*
 * See if the specified key is in the special "pairing" relationship with
 * the specified name.  We are called with key signing name.  The main point
 * is whether key has a name which matches.  If so, we return that name.
 * It is also necessary that name be self-signed, so we will check for that
 * here.  The signing key must be valid as well.
 */
static RingObject *
ringPairedName (RingObject *name, RingObject *key, RingSet const *set)
{
	RingObject			*keyname;	/* Names on key */
	RingObject			*namekey;	/* Key parent of name */
	RingObject			*namesig;	/* Sigs on name */
	PGPByte const		*smatchname; /* Actual name of *name */
	PGPByte const		*sname;		/* Actual name of *keyname */
	PGPSize			 	lmatchname; /* Length of smatchname */
	PGPSize				lname;		/* Length of sname */
	
	pgpAssert (OBJISKEY(key));
	pgpAssert (OBJISNAME(name));

	/* Check for key validity */
	if (key->k.trust & (PGP_KEYTRUSTF_REVOKED | PGP_KEYTRUSTF_EXPIRED))
		return NULL;
	
	/* Check that name is self-signed */
	namekey = name->n.up;
	pgpAssert (OBJISKEY(namekey));
	for (namesig = name->n.down; namesig; namesig = namesig->g.next) {
		if (!OBJISSIG(namesig))
			continue;
		/* XXX Should check expiration */
		if ((namesig->s.trust & PGP_SIGTRUSTF_CHECKED)
			&& !(namesig->s.trust & PGP_SIGTRUSTF_REVOKEDBYCRL)
			&& pgpIsRingSetMember(set, namesig)
			&& (namesig->s.type & 0xF0) == PGP_SIGTYPE_KEY_GENERIC) {
			break;				/* Exit with namesig nonnull on success */
		}
	}
	if (!namesig)				/* NULL namesig means no self sig */
		return NULL;
		
	/* Get userid string of name */
	smatchname = (PGPByte const *)ringFetchObject(set, name, &lmatchname);

	/* See if any names on keyname match */
	for (keyname = key->k.down; keyname; keyname = keyname->n.next) {
		if (!OBJISNAME(keyname))
			continue;
		sname = (PGPByte const *)ringFetchObject(set, name, &lname);
		if (lname == lmatchname && !memcmp (sname, smatchname, lname)) {
			/* Have a matching name! */
			return keyname;
		}
	}
	return NULL;
}


/*
 * Find all the paths from the starting name back to an axiomatically
 * trusted key.
 * pred holds the path which leads to the starting key from some target.
 * lastseg points at the last segment of the path, which already has
 * the key this name is on as the dest.  We just have to fill it in
 * and recurse, or check for buckstop keys.
 *
 * We reject paths which are to keys which have
 * already been processed as signing this key.  This can happen
 * if there are two names on a key, both signed by another key.  Otherwise
 * these would be treated as two different paths, but they
 * end up being identical.  The Maurer algorithm correctly accounts for this,
 * but it is a waste.  What we do is, for each signature, we check
 * all our earlier name siblings and see if they have a signature from the
 * same key.  If so we skip this sig.
 *
 * Returns	tail pointer for updated PathList
 *
 * name		starting name object for search backwards through web of trust
 * ppath	tail pointer of PathList to add our new paths to
 * predh	pointer to the (head of the) Path we will add to
 * predt	tail pointer to the Path we will add to (&newseg->tail)
 * depth	length of path so far, counting newseg (e.g. 1 at outer level)
 * maxdepth	maximum length of paths we allow
 * confset	ringset for trusted keys
 * allset	ringset for all keys
 * timenow	current timestamp
 * pool		ringpool to use for memory allocations
 * skipsigs list of signatures, chained by next, not to follow key of
 *
 */
static PathList **
ringFindPathsName (RingObject *name, PathList **ppath,
	Path **predh, Path **predt, unsigned depth,
    unsigned maxdepth, RingSet const *confset, RingSet const *allset,
	PGPUInt32 timenow, RingPool *pool, RingObject *skipsigs)
{
	RingObject     *sig,
	               *sigkey,
				   *pairedname,
				   *ssig;
	Path		   *newseg;
	Path          **newpredt;
	double			confidence;

	for (sig = name->g.down; sig; sig = sig->g.next) {
		if (!OBJISSIG(sig))
			continue;
		/* Skip if invalid sig */
		if (!(sig->s.trust & PGP_SIGTRUSTF_CHECKED)
			|| (sig->s.trust & PGP_SIGTRUSTF_REVOKEDBYCRL)
			|| !pgpIsRingSetMember((depth>1?confset:allset), sig)
			|| !mntSigIsValid(timenow, sig->s.tstamp, sig->s.sigvalidity)
			|| !mntSigOKWithRegexp( allset, &sig->s )
			|| (sig->s.type & 0xF0) != PGP_SIGTYPE_KEY_GENERIC)
			continue;
		/* Skip if signing key not in signer set */
		sigkey = sig->s.by;
		if (!pgpIsRingSetMember(confset, sigkey))
			continue;
		/* Skip if there is a newer valid sig by the same key */
		if (ringNewestValidSig (name, sigkey, (depth>1?confset:allset),
								timenow) != sig)
			continue;
		/* Skip if we have already done this key on an earlier sibling */
		if (depth>1 && ringEarlierValidSig (name, sigkey, confset, timenow))
			continue;
		/*
		 * Skip if signing key is in skipsigs list.  This is for the "paired
		 * keys" feature.
		 */
		for (ssig = skipsigs; ssig; ssig = ssig->g.next) {
			if (OBJISSIG(ssig) && sigkey == ssig->s.by)
				break;			/* Exit from loop with ssig nonnull on match */
		}
		if (ssig)				/* Non-null ssig means it was on skip list */
			continue;

		/* OK, investigate this signer further */
		if (sigkey->k.trust & PGP_KEYTRUSTF_BUCKSTOP
			&& !(sigkey->k.trust & (PGP_KEYTRUSTF_REVOKED |
											PGP_KEYTRUSTF_EXPIRED))
			/*&& !(key->k.trust & PGP_KEYTRUSTF_DISABLED)*/) {
			/* Found a path */
			ppath = pathListAddPathClone (ppath, *predh, pool);
			if (!ppath) {
				/* Out of memory */
				return NULL;
			}
		} else if (depth < maxdepth &&
				   !LOOKINGAT(&sigkey->k) &&
				   (confidence = pathKeyConfidence(sigkey, confset)) != 0) {
			/* Recurse */
			newseg = pathAlloc(pool);
			if (!newseg) {
				/* Out of memory */
				return NULL;
			}
			newseg->dest = name->g.up;
			newseg->src = sigkey;
			newseg->next = NULL;
			newseg->confidence = confidence;
			newpredt = pathAddSeg (predt, newseg);
			ppath = ringFindPathsKey (sigkey, ppath, predh, newpredt,
					 depth+1, maxdepth, confset, allset, timenow, pool);
			pathFree (newseg, pool);
			*predt = NULL;
			if (!ppath) {
				/* Out of memory */
				return NULL;
			}
		} else if (depth < maxdepth &&
				   !LOOKINGAT(&sigkey->k) &&
				   (pairedname =
						ringPairedName(name, sigkey, confset)) != NULL) {
			/*
			 * We have a signature by a sibling key, one which matches our
			 * name.  Recurse from that name.  The resulting path element
			 * will have as source, signer of that paired name, and as
			 * destination, this key.  Even though there is no "actual"
			 * signature in such a form, there is an implied signature.
			 * We won't increment depth in this case.
			 * Here we use the skipsigs feature - we don't want to follow
			 * any sigs from our pair which we are also following here.
			 * This is the only place it is used (at this writing!).
			 */