pgputilrandompool.c

PGP8.0源码 请认真阅读您的文件包然后写出其具体功能

/*__________________________________________________________________________
 Copyright (C) 2002 PGP Corporation
 All rights reserved.

 $Id: pgpUtilRandomPool.c,v 1.5 2002/08/06 20:11:19 dallen Exp $
__________________________________________________________________________*/

/*
 * True random number computation and storage
 *
 * Written 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.
 */

#ifndef PGPSDK_DRIVER
#define PGPSDK_DRIVER	0
#endif

#if PGPSDK_DRIVER
#define PGP_WIN32 			1
#define kPGPError_NoErr		0
#define pgpAssert(s)
#define DEBUG_STRUCT_CONSTRUCTOR(type)

#include <memory.h>
#pragma intrinsic(memcpy)
#define pgpCopyMemory(src,dst,i)	 memcpy(dst,src,i)
#endif //PGPSDK_DRIVER

#if PGPSDK_DRIVER
#include  "pgpUtilConfig.h"
#else
#include  "pgpConfig.h"
#endif

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

#if PGPSDK_DRIVER
#include "pgpUtilBase.h"
#include "pgpSHA.h"
#else
#include "pgpBase.h"
#include "pgpSHA.h"
#include "pgpMem.h"
#include "pgpRnd.h"

#include "pgpDebug.h"
#include "pgpRandomPoolPriv.h"
#include "pgpRndSeed.h"
#include "pgpRMWOLock.h"
#endif //!PGPSDK_DRIVER

/* 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	(32*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;

#if !PGPSDK_DRIVER
	PGPRMWOLock	criticalLock;
#endif

} RandomPool;

/* This is the global random pool */
static RandomPool	sPool	= {0,};
#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;

#if !PGPSDK_DRIVER
	InitializePGPRMWOLock( &pool->criticalLock );
#endif

	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;
	}
}

#if !PGPSDK_DRIVER

/*
 * 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;
}
#endif  //!PGPSDK_DRIVER




/*
 * 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) : "ax")
#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;
	unsigned		n;
	RandomPool	*	pool	= GetPool();

	if (delta < 1 << DERATING)
		return 0;

	n = 31-DERATING;
	if (!(delta & 0xffff0000))
		delta <<= 16, n -= 16;
	if (!(delta & 0xff000000))
		delta <<= 8, n -= 8;
	if (!(delta & 0xf0000000))
		delta <<= 4, n -= 4;
	if (!(delta & 0xc0000000))
		delta <<= 2, n -= 2;
	if (!(delta & 0x80000000))
		delta <<= 1, n -= 1;
	pgpAssert(n < 32);

	/* Lose high-order bit of delta */
	pgpAssert(delta & 0x80000000);
	delta <<= 1;

	frac = pool->randKeyFrac;
	UMULH_32(t,delta,frac);
	if ((frac += t) < t) {
		if ((frac += delta) < delta)
			frac = (frac >> 1) + 0x80000000ul;
		else
			frac >>= 1;
		n++;
	} else if ((frac += delta) < delta) {
		frac >>= 1;
		n++;
	}

	/* The timers used are very high-resolution. Be
	** conservative with our estimates. No more than
	** 10 bits per sample.
	*/

	if( n > 10 )
		n = 10;

	/* Store back updated fractional bits */
	pool->randKeyFrac = frac;

	/* n is now the count of whole bits */
	if ((pool->randKeyBits += n) >= RANDKEYBITS) {
		/* Overflow - saturate at RANDKEYBITS */
		pool->randKeyBits = RANDKEYBITS;
		pool->randKeyFrac = 0;
	}

	return n;
}

#if !PGPSDK_DRIVER
	PGPUInt32
PGPGlobalRandomPoolGetEntropy()
{
	PGPUInt32	randBits;
	RandomPool	*pool = GetPool();

	PGPRMWOLockStartReading( &pool->criticalLock );
		randBits = pool->randBits;
	PGPRMWOLockStopReading( &pool->criticalLock );

	return( randBits );
}

	PGPUInt32
PGPGlobalRandomPoolGetSize()
{