pgprngmnt.c

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

/*
 * 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.
 *
 * Copyright (C) 1994-1997 Pretty Good Privacy, Inc. All rights reserved.
 *
 * Written by Colin Plumb
 *
 * $Id: pgpRngMnt.c,v 1.33.2.10 1997/06/07 09:50:36 mhw Exp $
 */
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

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

#include "pgpDebug.h"
#include "pgpMakeSig.h"
#include "pgpPktByte.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 "pgpHash.h"
#include "pgpErr.h"
#include "pgpPubKey.h"
#include "pgpRngRead.h"	/* for ringFetchObject */
#include "pgpSig.h"
#include "pgpSigSpec.h"
#include "pgpUsuals.h"
#include "pgpTypes.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. And the
* set of keys looked at is not pre-selected to be limited to the
* trusted introducers. That last change should be done before
* enabling this code.
*
* 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.)
*/



/*
* Check to see if the signature is valid 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.
*
* An intelligent 8086 or 68000 compiler would evaluate the division by
* 86400 = 675 * 128 as (x>>7)/675, which can use a 32/16 bit divide
* (which can't overflow), but I'd be surprised if any PC compilers
* actually did it that way.
*/
static int
mntSigIsValid(word32 timenow, word32 tstamp, unsigned validity)
{
	return
	(timenow <= tstamp || (unsigned)((timenow-tstamp)/86400) <= validity-1u);
}


#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.
*/

/* This is a path or a path segment. next->src may not equal dest. */
	typedef struct Path {
		struct Path	*next;
		RingObject	*src,
			*dest;
		double	confidence;
	} Path, *pPath;

/* This is a list of paths. Some segments may be on multiple paths. */
typedef struct PathList {
		struct PathList	*next;
		Path	*path;
	Path **ptail;
		double	confidence;
	} PathList, *pPathList;

	#undef DEBUGPATH

	#ifdef DEBUGPATH

static char const hexchar[16] = {
	'0','1','2','3','4','5','6','7',
	'8','9','A','B','C','D','E','F'
};

static int
ringTtyPrintKeyID(FILE *f, RingObject *key)
{
	byte *buf;
	int i;

	pgpAssert (OBJISKEY(key));
	buf = key->k.keyID;
	for (i = 4; i < 8; i++) {
		putc(hexchar[buf[i] >> 4 & 15], f);
		putc(hexchar[buf[i] & 15], f);
	}
	return 8;
}

static int
ringTtyPrintKeyName(FILE *f, RingObject *key, RingPool *pool)
{
	RingSet *set = ringSetCreate(pool);
	char const *sname;
	char bname[256];
	size_t len;

	key = key->g.down;
	while (!OBJISNAME(key)) {
		key = key->g.next;
	}
	ringSetAddObject (set, key);
	sname = ringNameName (set, key, &len);
	strncpy (bname, sname, len);
	bname[len] = '\0';
	fputs (bname, f);
	ringSetDestroy (set);
	return 0;
}

static int
ringTtyPrintKey(FILE *f, RingObject *key, RingPool *pool)
{

	ringTtyPrintKeyID (f, key);
	fprintf (f, "(");
	ringTtyPrintKeyName (f, key, pool);
	fprintf (f, ")");
	return 0;
}

static void
ringTtyPrintPath(FILE *f, Path *path, RingPool *pool)
{
	fprintf (f, " Path ");
	while (path) {
		fprintf (f, "from ");
		ringTtyPrintKey (f, path->src, pool);
		fprintf (f, " to ");
		ringTtyPrintKey (f, path->dest, pool);
		fprintf (f, ", conf: %g\n", path->confidence);
		path = path->next;
		if (path)
			fprintf (f, "  ...segment ");
	}
}

static void
ringTtyPrintPathList(FILE *f, PathList *pl, RingPool *pool)
{
	fprintf (f, "Begin PathList\n");
	while (pl) {
		fprintf (f, " (conf=%g) ", pl->confidence);
		ringTtyPrintPath (f, pl->path, pool);
		pl = pl->next;
	}
	fprintf (f, "End PathList\n");
}

#endif /* DEBUGPATH */


/* Allocate a Path segment */
static Path *
pathAlloc (RingPool *pool)
{
	Path *path = pool->paths;

	if (path) {
	pool->paths = path->next;
	} else {
		path = memPoolAlloc (&pool->pathpool, sizeof(struct Path),
			alignof(struct Path));
	}
	return path;
}

/* Free a Path segment */
static void
pathFree (Path *path, RingPool *pool)
{
	path->next = pool->paths;
	pool->paths = path;
}