pgprngmnt.c

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

/* Free an entire Path */
static void
pathFreeAll (Path *phead, RingPool *pool)
{
	Path **ptail = &phead->next;
	while (*ptail) {
		ptail = &(*ptail)->next;
	}
	*ptail = pool->paths;
	pool->paths = phead;
}

/* Allocate a PathList element */
static PathList *
pathListAlloc (RingPool *pool)
{
	PathList *plist = pool->pathlists;

	if (plist) {
		pool->pathlists = plist->next;
		plist->next = NULL;
	} else {
		plist = memPoolAlloc (&pool->pathpool, sizeof(struct PathList),
		alignof(struct PathList));
	}
	return plist;
}

/* Free a PathList element, also freeing any path it points to */
static void
pathListFree (PathList *plist, RingPool *pool)
{
	if (plist->path)
		pathFreeAll (plist->path, pool);
	plist->path = 0;
	plist->confidence = 0.;
	plist->next = pool->pathlists;
	pool->pathlists = plist;
}

/* Free a whole PathList, also freeing the Paths it points to */
static void
pathListFreeAll (PathList *plhead, RingPool *pool)
{
	PathList **pltail = &plhead->next;
	while (*pltail)
		pltail = &(*pltail)->next;
	*pltail = pool->pathlists;
	pool->pathlists = plhead;
	while (plhead != *pltail) {
		pathFreeAll (plhead->path, pool);
		plhead->path = 0;
		plhead->confidence = 0.;
		plhead = plhead->next;
	}
}


/* Add a Path segment to a Path
*
* Returns	updated Path tail pointer
*
* tail		 tail pointer for Path to be added to
* seg		 pointer to Path segment to add
*
*/
static Path **
pathAddSeg (Path **tail, Path *seg)
{
	seg->next = *tail;
	*tail = seg;
	return &seg->next;
}

/*
* Make a copy of a Path, leaving the original untouched. Optionally return a
* pointer to the tail of the new Path.
*
* Returns	pointer to new cloned path
*
* p1		pointer to the path to be cloned
* ptl		 optional return parameter for tail pointer of new path
* pool		 ringpool used for allocations of new path segments
*
*/
static Path *
pathClone (Path *p1, Path ***ptl, RingPool *pool)
{
	Path *phead,
	**ptail = &phead;

	while (p1) {
		*ptail = pathAlloc(pool);
		if (!*ptail)
			return NULL;
		**ptail = *p1;
		p1 = p1->next;
		ptail = &(*ptail)->next;
	}
	if (ptl)
		*ptl = ptail;
	return phead;
}


/* Add a copy of a Path to the PathList
*
* Returns	tail pointer of updated PathList
*
* tail		 tail pointer of PathList to be added to
* path		 pointer to Path to add to the PathList
* pool		 ringpool to use for memory allocations
*
*/
static PathList **
pathListAddPathClone (PathList **tail, Path *path, RingPool *pool)
{
	PathList *pl;

	pl = pathListAlloc(pool);
	if (!pl)
		return NULL;
	pl->path = pathClone (path, &pl->ptail, pool);
	pl->next = *tail;
	*tail = pl;
	return &pl->next;
}


/* Calculate the confidence associated with a path. */
static double
pathConfidence (Path *path)
{
	double conf = 1.0;

	while (path) {
		conf *= path->confidence;
		path = path->next;
	}
	return conf;
}

/*
* Prune the PathList to keep only the highest-confidence pathmax Paths.
* Return the new PathList, free the no longer used Paths.
*
* Returns	new PathList with no more than pathmax paths
*
* plist	 PathList to be pruned
* pathmax	maximum number of paths to allow
* pool		 ringpool to use for memory allocations
*
*/
static PathList *
pathListPrune (PathList *plist, unsigned pathmax, RingPool *pool)
{
	PathList *iplist;			/* Copy of plist */
	PathList **pl1,		 	/* Iterator over plist */
	**maxpl1;			/* Max confidence pl1 pointer */
	PathList *nplist,			/* New pathlist head */
	**nptail;			/* New pathlist tail */
	unsigned npaths,		 	/* Number of paths in plist initially */
	newnpaths;		/* Number of paths in final nplist */
	double maxconf;		 /* Best confidence value so far */

	/* Calculate confidence value for each path */
	iplist = plist;
	npaths = 0;
	while (plist) {
		npaths += 1;
		plist->confidence = pathConfidence (plist->path);
		plist = plist->next;
		}
		plist = iplist;

		/* Initialize the new path list */
		nplist = NULL;
		nptail = &nplist;
		newnpaths = min (pathmax, npaths);
		while (newnpaths--) {
			 /* Add the best path from plist to nplist */
			 pl1 = &plist;
			 maxconf = 0.;
			 maxpl1 = pl1;
			 while (*pl1) {
			 	/* Find best path in plist in **maxpl1 */
			 	if ((*pl1)->confidence > maxconf) {
			 		 maxconf = (*pl1)->confidence;
			 		 maxpl1 = pl1;
			 	}
			 	pl1 = &(*pl1)->next;
			 }
			 *nptail = *maxpl1;
			 *maxpl1 = (*maxpl1)->next;
			 nptail = &(*nptail)->next;
			 *nptail = NULL;
		}

		if (plist)
			 pathListFreeAll (plist, pool);
		return nplist;
	}


	/*
* Append a (copy of a) second path to the first, removing common segments.
* Return pointer to "next" pointer of last segment (and pass that as ptail)
*
* Return	tail pointer for updated Path
*
* phead	 pointer to Path which gets appended to
* ptail	 tail pointer for Path which gets appended to
* p2		pointer to Path to append (a copy of)
* pool		 ringpool to use for memory allocations
*
*/
static Path **
pathUnion (Path *phead, Path **ptail, Path *p2, RingPool *pool)
{
	Path *p1;
	Path **iptail = ptail;

	/* Add path p2 but skip those segments in p1 */
	for ( ; p2; p2 = p2->next) {
		p1 = phead;
		for (p1=phead; p1 && p1 != *iptail; p1 = p1->next) {
			/* Eliminate path segments which are in there already */
			if (p2->src == p1->src && p2->dest == p1->dest) {
				/* Make sure our confidence rules are working */
				pgpAssert (p2->confidence == p1->confidence);
				break;
			}
		}
		if (p1 && p1 != *iptail)
			continue;
		*ptail = pathAlloc(pool);
		if (!*ptail)
			return NULL;
		**ptail = *p2;
		ptail = &(*ptail)->next;
		*ptail = NULL;
	}
	return ptail;
}

/*
* Calculate the confidence for a list of paths. We add the confidence for
* each path, subtrace the confidence for the unions of all pairs of paths,
* add the confidence for the unions for all the triples, and so on.
* We actually do this by taking each subset of the paths, unioning them,
* calculating the confidence for that path, and adding or subtracting it
* based on the parity.
*/
static double
pathListConfidence (PathList *plist, RingPool *pool)
{
		unsigned	pathcount,
			mask,
				tmask;
		PathList	*iplist = plist;
		double	conf = 0.;

#ifdef DEBUGPATH
	fprintf (stdout, "Maurer alg:\n");
#endif

	pathcount = 0;
	while (plist) {
		++pathcount;
		plist = plist->next;
	}
	plist = iplist;

	pgpAssert (pathcount < sizeof(unsigned) * 8);
	for (mask=1; mask < (1U<<pathcount); ++mask) {
		double pathconf;
		Path *phead=NULL, **ptail=&phead;
		int oddparity = 0;
		plist = iplist;
		tmask = mask;
		while (plist && tmask) {
			if (tmask & 1) {
				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,
			maxvalidconfidence = 0.;
		word16	maxvalidity = 0;
	int				allvalid = 1;		 /* True if all names have validity */
	ringmask const	mask = set->mask;

	for (name = key->g.down; name; name = name->g.next) {
		if (!OBJISNAME(name) || !(name->g.mask & mask))
			continue;
		if (name->n.confidence == PGP_NEWTRUST_UNDEFINED)
			continue;
		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 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)
		return maxvalidconfidence;
	else
#endif
		return minconfidence;
}