pgprandompool.c

vc环境下的pgp源码

/*
 * True random number computation and storage
 *
 * Wrtten by Colin Plumb.
 *
 * This performs a strong hash on the data as it is fed into the
 * pool, and the pool is again strongly hashed to produce the output
 * of the random-number generator.  This is overkill, as either step
 * should produce high-quality numbers.
 *
 * $Id: pgpRandomPool.c,v 1.20.6.1 1999/06/04 01:52:26 heller Exp $
 */
#include  "pgpConfig.h"

#include <stdlib.h>
#include <string.h>

#include "pgpBase.h"
#include "pgpMem.h"

#include "pgpSHA.h"
#include "pgpRnd.h"

#include "pgpDebug.h"
#include "pgpRandomPoolPriv.h"
#include "pgpRndSeed.h"
#include "pgpRMWOLock.h"

/* We import the following things from the SHA code */
#define HashTransform pgpSHATransform
#define HASH_INWORDS 16
#define HASH_OUTWORDS 5

/*
 * The pool must be a multiple of the hash input size and the hash
 * output size.  For SHA, these are 16 and 5 words, respectively,
 * so the pool must be a multiple of 80 words.  If the hash were
 * MD5, it would have to be a multiple of 16 and of 4, or a multiple
 * of 16 all together.  (80 words is 2560 bits.)
 */
#define RANDPOOLWORDS 160	/* 5,120 bits */
#define RANDPOOLBITS (32*RANDPOOLWORDS)
#if RANDPOOLWORDS % HASH_OUTWORDS
#error RANDPOOLWORDS must be a multiple of HASH_OUTWORDS
#endif
#if RANDPOOLWORDS % HASH_INWORDS
#error RANDPOOLWORDS must be a multiple of HASH_INWORDS
#endif

#define RANDKEYBITS	(8*HASH_INWORDS)

/* minimum number of bytes to consider the random pool seeded */
#define kMinimumSeedBytes		24
#define kMinimumSeedBits		( 8 * kMinimumSeedBytes )

typedef struct RandomPool
{
	/*
	 * Accumulators to estimate entropy in the pool.
	 * See comments with pgpGlobalRandomPoolEntropyWasAdded for how
	 * fractional bits are stored.
	 */
	PGPUInt32	randBits; /* Bits of entropy in pool */
	PGPUInt32	randFrac; /* Fraction of a bit of entropy in pool */
	PGPUInt32	randInBits; /* Bits of entropy added to pool */

	/* Estimate entropy in randKey array, a buffer which dumps into pool */
	PGPUInt32	randKeyBits; /* Bits of entropy in randKey */
	PGPUInt32	randKeyFrac; /* Fraction of a bit of entropy in randKey */

	/* Must be word-aligned, so make it words.  Cast to bytes as needed. */
	PGPUInt32	randPool[RANDPOOLWORDS];	/* Random pool */
	PGPUInt32	randPoolAddPos;	/* Position to encrypt into (words) */

	PGPUInt32	randKey[HASH_INWORDS];	/* Random input buffer */
	PGPUInt32	randKeyAddPos;	/* Position to add to (bytes) */

	PGPUInt32	randOut[HASH_OUTWORDS];	/* Random output buffer */
	PGPUInt32	randOutGetPos; /* Position to get from (b) */

	/* Keeps track of when we need to do another hashing step */
	PGPUInt32	randHashCounter;
	
	PGPRMWOLock	criticalLock;
		
} RandomPool;

/* This is the global random pool */
static RandomPool	sPool;
#define GetPool()		( &sPool )

static void sRandAddKeyEntropy( RandomPool *pool );


	PGPError
pgpInitGlobalRandomPool()
{
	RandomPool *	pool	= NULL;
	
	pool	= GetPool();
	
	pool->randBits			= 0;
	pool->randFrac			= 0;
	pool->randInBits		= 0;
	pool->randKeyBits		= 0;
	pool->randKeyFrac		= 0;
	pool->randPoolAddPos	= 0;
	pool->randKeyAddPos		= 0;
	pool->randOutGetPos		= sizeof( pool->randOut);
	pool->randHashCounter	= 0;
	
	InitializePGPRMWOLock( &pool->criticalLock );
	
	return( kPGPError_NoErr );
}

/*
 * To mix input into the pool, we insert it into a key buffer and then
 * use the key buffer to CBC-encrypt the pool.  Actually, to make sure
 * that the input (which includes such sensitive information as passphrase
 * keystrokes) is not left in memory, we XOR it with the old contents of
 * the key buffer along with some of the the data about to be encrypted.
 * Since none of the disguising data depends on the byte, this does
 * not destroy any entropy inherent in the input byte.
 *
 * To reduce burstiness in the timing, rather than wait until the key
 * buffer is full to encrypt the entire pool, we update part of the key
 * and then encrypt part of the pool.  The randHashCounter keeps track
 * of what's going on to ensure that a byte of key is not overwritten
 * until it has participated in the encryption of every block of the pool.
 *
 * The pool contains RANDPOOLWORDS/HASH_OUTWORDS blocks.  We must do
 * that many hash-encryption steps before 4*HASH_INWORDS bytes of the
 * key have been overwritten.  So randHashCounter is incremented by
 * RANDPOOLWORDS/HASH_OUTWORDS each time a byte is added to the
 * randKey array, and it is decreased by 4*HASH_INWORDS each time we
 * do a hash-encryption step.  This keeps the two processes in
 * balance.
 *
 * We store entropy in the randKey array until some minimum is
 * reached, or until we have filled the entire randKey array, then we
 * dump the entropy into the randPool as just described.  This
 * prevents an attacker who knows the initial seed value and who has
 * access to the output of the randPool from guessing the input values
 * by trying all possibilities.
 *
 * The bits deposited need not have any particular distribution; the
 * stirring operation transforms them to uniformly-distributed bits.
 */
	static void
sRandPoolAddByte(
	RandomPool *	pool,
	PGPByte			b)
{
	int				i;
	PGPUInt32		pos;

	/* Mix new byte into pool */
	((PGPByte *)pool->randKey)[pool->randKeyAddPos] ^= b;
	if (++pool->randKeyAddPos == sizeof(pool->randKey))
		pool->randKeyAddPos = 0;

	/*
	 * If we've reached the end of a word, mask the next word with
	 * a soon-to-be-overwritten byte of the pool.  With a 64-byte input
	 * hash, this will use a different word for masking each of the
	 * 16 words as long as there are at least 16 output blocks
	 * (64 words at 4 words per output block, or 512 bits total) in the
	 * pool.  Just to be sure, let's enforce it...
	 */
#if HASH_INWORDS > RANDPOOLWORDS / HASH_OUTWORDS
#error Please make RANDPOOLWORDS bigger than HASH_INWORDS * HASH_OUTWORDS.
#endif
	if (pool->randKeyAddPos % sizeof(PGPUInt32) == 0)
		*(PGPUInt32 *)((PGPByte *)pool->randKey + pool->randKeyAddPos) ^=
		                            pool->randPool[pool->randPoolAddPos];

	/* Do a hashing step if required */
	pool->randHashCounter += RANDPOOLWORDS/HASH_OUTWORDS;

	/* Update pool every 64 bits of entropy, or when about to wrap around */
	if (pool->randKeyBits >= 64 ||
		pool->randHashCounter >= 4*HASH_INWORDS*RANDPOOLWORDS/HASH_OUTWORDS) {
		while (pool->randHashCounter >= 4*HASH_INWORDS) {
			pool->randHashCounter -= 4*HASH_INWORDS;

			/* CBC-encrypt the current block */
			pos = pool->randPoolAddPos;
			HashTransform(pool->randPool + pos, pool->randKey);

			/* Get the offset of the next block and XOR this one in */
			pool->randPoolAddPos = pos + HASH_OUTWORDS;
			if (pool->randPoolAddPos == RANDPOOLWORDS)
				pool->randPoolAddPos = 0;
			for (i = 0; i < HASH_OUTWORDS; i++)
				pool->randPool[pool->randPoolAddPos + i] ^=
													pool->randPool[pos+i];
		}
		/* Accumulate entropy from key into pool */
		sRandAddKeyEntropy( pool );
	}
}

/*
 * Make a deposit of information (entropy) into the pool.
 */
	static void
sRandPoolAddBytes(
	void *			priv,
	PGPByte const *	p,
	unsigned		len)
{
	RandomPool *pool	= GetPool();
	
	pgpAssert( pool );

	(void)priv;

	while (len--) {
		sRandPoolAddByte( pool, *p++ );
	}

	/* Pool has changed, randOut is out of date */
	pool->randOutGetPos = sizeof(pool->randOut);
}

static void
sRandGetOutput( RandomPool *	pool )
{
	int i;

	/*
	 * Hash the pending input and the entire pool, with the old
	 * randOut as IV.
	 */
	HashTransform( pool->randOut, pool->randKey );
	for (i = 0; i < RANDPOOLWORDS; i += HASH_INWORDS)
		HashTransform( pool->randOut, pool->randPool + i );

	/* Okay, we can now fetch starting at the beginning of randOut */
	pool->randOutGetPos = 0;
}

/*
 * Withdraw some bits from the pool.  Regardless of the distribution of the
 * input bits, the bits returned are uniformly distributed, although they
 * cannot, of course, contain more Shannon entropy than the input bits.
 */
	static void
sRandPoolGetBytesEntropy(
	void *			priv,
	PGPByte *		buf,
	unsigned		len,
	unsigned		bits)
{
	RandomPool *pool	= GetPool();
	unsigned t;
	
	pgpAssert( pool );

	(void)priv;

	if (pool->randBits >= bits)
		pool->randBits -= bits;
	else
		pool->randFrac = pool->randBits = 0;

	while (len > (t = sizeof(pool->randOut) - pool->randOutGetPos)) {
		pgpCopyMemory( (PGPByte *)pool->randOut + pool->randOutGetPos, buf, t);
		buf += t;
		len -= t;
		sRandGetOutput( pool );
	}

	if (len) {
		pgpCopyMemory( (PGPByte *)pool->randOut+pool->randOutGetPos, buf, len);
		pool->randOutGetPos += len;
	}
}


/*
 * Destroys already-used random numbers.  Ensures no sensitive data
 * remains in memory that can be recovered later.  This repeatedly
 * mixes the output of the generator back into itself until all internal
 * state has been overwritten.
 */
	static void
sRandPoolStir(void *	priv )
{
	RandomPool *pool	= GetPool();
	unsigned	i;
	
	pgpAssert( pool );

	(void)priv;

	for (i = 0; i < 5*sizeof(pool->randKey)/sizeof(pool->randOut); i++) {
		sRandPoolAddBytes(priv, (PGPByte *)pool->randOut,
						  sizeof(pool->randOut));
		sRandGetOutput( pool );
	}
}

	static void
sRandPoolAddBytesLock(
	void *			priv,
	PGPByte const *	p,
	unsigned		len)
{
	RandomPool *pool	= GetPool();
	
	PGPRMWOLockStartWriting( &pool->criticalLock );
		sRandPoolAddBytes( priv, p, len );
	PGPRMWOLockStopWriting( &pool->criticalLock );
}

	static void
sRandPoolGetBytesEntropyLock(
	void *			priv,
	PGPByte *		buf,
	unsigned		len,
	unsigned		bits)
{
	RandomPool *pool	= GetPool();
	
	PGPRMWOLockStartWriting( &pool->criticalLock );
		sRandPoolGetBytesEntropy( priv, buf, len, bits );
	PGPRMWOLockStopWriting( &pool->criticalLock );
}

	static void
sRandPoolStirLock(void *priv)
{
	RandomPool *pool	= GetPool();
	
	PGPRMWOLockStartWriting( &pool->criticalLock );
		sRandPoolStir( priv );
	PGPRMWOLockStopWriting( &pool->criticalLock );
}

static const PGPRandomVTBL sGlobalRandomPoolVTBL =
{
	"Global true random-number pool",
	sRandPoolAddBytesLock,
	sRandPoolGetBytesEntropyLock,
	sRandPoolStirLock
};


	PGPRandomVTBL const *
pgpGetGlobalRandomPoolVTBL( void )
{
	return( &sGlobalRandomPoolVTBL );
}


/*
 * Used for cases where we want to create a temporary PGPRandomContext
 * which wraps the random pool.
 */
	void
pgpInitGlobalRandomPoolContext( PGPRandomContext *rc )
{
	rc->context	= NULL;
	rc->vtbl	= pgpGetGlobalRandomPoolVTBL();
	rc->priv	= NULL;
	rc->destroy	= NULL;
}




/*
 * True random bit accumulation.  These are extra functions exported
 * for entropy estimation.
 *
 * Entropy is expressed in terms of a delta, essentially the difference
 * between the observed value and the expected value, whose logarithm
 * is a measure of entropy.  (The logarithm to the base 2 is entropy
 * expressed in bits.)
 *
 * The internal amount-of-entropy accumulator is maintained in two
 * halves: a counter of bits, and a fraction of a bit, expressed
 * in the form of a normalized delta.  If 0 <= f < 1 is a fraction
 * of a bit, then 1 <= 2^f < 2, so it's remembered as
 * 0 <= x = 2^f - 1 < 1, a fixed-point number.
 *
 * Given a new fractional-bit delta, 1+y in similar form (obtained
 * by normalizing the delta into the desired form), the output
 * fractional bit delta 1+z = (1+x) * (1+y).  If this exceeds 2,
 * divide it by 2 and add a full bit to the bit counter.
 *
 * The implementation, of course, actually computes z = x + y + x*y,
 * where 0 <= z < 3.  This can be done by adding each of the three terms
 * (each of which is less than 1) and noticing the overflow.  If the
 * addition does not overflow, z < 1 and nothing needs to be done.
 *
 * If one addition overflows, 1 <= z < 2, but after overflow we get
 * z-1.  We want (1+z)/2-1 = (z-1)/2, so just divide the result of
 * the wrapped addition by 2.
 *
 * If both additions overflow, the addition wraps to z-2, but we
 * still want (z-1)/2 = (z-2)/2 + 1/2, so divide the wrapped result
 * by 2 and add 1/2.
 *
 * Due to the way that the fixed-point numbers are stored, the x*y part is
 * the high half of the 32-bit unsigned product of x and y.  This can be
 * safely underestimated if desired, if a 64-bit product is difficult to
 * compute.
 *
 * The simplest snd safest definition is
 * #define UMULH_32(r,a,b) (r) = 0
 */
#ifndef UMULH_32
#if defined(__GNUC__) && defined(__i386__)
/* Inline asm goodies */
#define UMULH_32(r,a,b) __asm__("mull %2" : "=d"(r) : "%a"(a), "mr"(b))
#elif HAVE64
#define UMULH_32(r,a,b) ((r) = (PGPUInt32)((word64)(a) * (b) >> 32))
#else
/* Underestimate the product */
#define UMULH_32(r,a,b) ((r) = ((a) >> 16) * ((b) >> 16))
#endif
#endif /* !UMULH_32 */

#define DERATING 2	/* # of bits to underestimate */

	static PGPUInt32
pgpGlobalRandomPoolEntropyWasAdded(
	PGPUInt32		delta )
{
	PGPUInt32		frac,
					t;