bsd/dev/random/YarrowCoreLib/src/prng.c

/*
 * Copyright (c) 1999, 2000-2001 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 *
 * The contents of this file constitute Original Code as defined in and
 * are subject to the Apple Public Source License Version 1.1 (the
 * "License").  You may not use this file except in compliance with the
 * License.  Please obtain a copy of the License at
 * http://www.apple.com/publicsource and read it before using this file.
 *
 * This Original Code and all software distributed under the License are
 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License.
 *
 * @APPLE_LICENSE_HEADER_END@
 */

/*
	File:		prng.c

	Contains:	Core routines for the Counterpane Yarrow PRNG.

	Written by:	Counterpane, Inc.

	Copyright: (c) 2000 by Apple Computer, Inc., all rights reserved.

	Change History (most recent first):

		02/10/99	dpm		Created, based on Counterpane source.

*/
/*
	prng.c

	Core routines for the Counterpane PRNG
*/
#include "userdefines.h"
#include "assertverify.h"
#include "dev/random/YarrowCoreLib/include/yarrowUtils.h"

#if		defined(macintosh) || defined(__APPLE__)
/* FIXME - this file needs to be in a platform-independent place */

#include "macOnly.h"
#endif	/* macintosh */
#include "smf.h"
#include "sha1mod.h"
#include "entropysources.h"
#include "comp.h"
#include "dev/random/YarrowCoreLib/include/yarrow.h"
#include "prng.h"
#include "prngpriv.h"


#define _MAX(a,b) (((a)>(b))?(a):(b))
#define _MIN(a,b) (((a)<(b))?(a):(b))

#if		defined(macintosh) || defined(__APPLE__)
/*
 * No mutexes in this module for Macintosh/OSX. We handle the
 * required locking elsewhere.
 */
#define MUTEX_ENABLE	0

#include <string.h>		/* memcpy, etc. */
#if		TARGET_API_MAC_OSX
	#include <sys/time.h>		/* for timespec */
#elif	TARGET_API_MAC_CARBON
	#include <Timer.h>				/* Microseconds */
	#include <Math64.h>
#elif	KERNEL_BUILD
    #include <sys/time.h>
#else
	#error Unknown TARGET_API
#endif	/* TARGET_API */
#else
#define MUTEX_ENABLE	1
#endif	/* macintosh */

#if		MUTEX_ENABLE
static HANDLE Statmutex = NULL;
static DWORD mutexCreatorId = 0;
#endif

#pragma mark -
#pragma mark * * * Static Utility functions * * *

/* All error checking should be done in the function that calls these */

/*
 * out := SHA1(IV | out)
 */
static void
prng_do_SHA1(GEN_CTX *ctx)
{
	SHA1_CTX sha;

	SHA1Init(&sha);
	SHA1Update(&sha,ctx->IV,20);
	SHA1Update(&sha,ctx->out,20);
	SHA1Final(ctx->out,&sha);
	ctx->index = 0;
}

/*
 * IV  := newState
 * out := SHA1(IV)
 *
 * Called from init, prngForceReseed(), and prngOutput()
 * as anti-backtracking mechanism.
 */
static void
prng_make_new_state(GEN_CTX *ctx,BYTE *newState)
{
	SHA1_CTX sha;

	memcpy(ctx->IV,newState,20);
	SHA1Init(&sha);
	SHA1Update(&sha,ctx->IV,20);
	SHA1Final(ctx->out,&sha);
	ctx->numout = 0;
	ctx->index = 0;
}

#if		SLOW_POLL_ENABLE


/* Initialize the secret state with a slow poll */
/* Currently only called from prngInitialize */

#define SPLEN 65536  /* 64K */

static void
prng_slow_init(PRNG *p)
/* This fails silently and must be fixed. */
{
	SHA1_CTX* ctx = NULL;
	MMPTR mmctx = MM_NULL;
	BYTE* bigbuf = NULL;
	MMPTR mmbigbuf = MM_NULL;
	BYTE* buf = NULL;
	MMPTR mmbuf = MM_NULL;
	DWORD polllength;

	mmbigbuf = mmMalloc(SPLEN);
	if(mmbigbuf == MM_NULL) {goto cleanup_slow_init;}
	bigbuf = (BYTE*)mmGetPtr(mmbigbuf);

	mmbuf = mmMalloc(20);
	if(mmbuf == MM_NULL) {goto cleanup_slow_init;}
	buf = (BYTE*)mmGetPtr(mmbuf);

	mmctx = mmMalloc(sizeof(SHA1_CTX));
	if(mmctx == MM_NULL) {goto cleanup_slow_init;}
	ctx = (SHA1_CTX*)mmGetPtr(mmctx);


	/* Initialize the secret state. */
	/* Init entropy pool */
	SHA1Init(&p->pool);
	/* Init output generator */
	polllength = prng_slow_poll(bigbuf,SPLEN);
	SHA1Init(ctx);
	SHA1Update(ctx,bigbuf,polllength);
	SHA1Final(buf,ctx);
	prng_make_new_state(&p->outstate, buf);

cleanup_slow_init:
	mmFree(mmctx);
	mmFree(mmbigbuf);
	mmFree(mmbuf);

	return;
}

#endif	/* SLOW_POLL_ENABLE */

/* In-place modifed bubble sort */
static void
bubbleSort( UINT *data, LONG len )
{
	LONG 	i,last,newlast;
	UINT	temp;

	last = len-1;
	while(last!=-1)
	{
		newlast = -1;
		for(i=0;i<last;i++)
		{
			if(data[i+1] > data[i])
			{
				newlast = i;
				temp = data[i];
				data[i] = data[i+1];
				data[i+1] = temp;
			}
		}
		last = newlast;
	}
}

#pragma mark -
#pragma mark * * * Public functions * * *

/* Set up the PRNG */
prng_error_status
prngInitialize(PrngRef *prng)
{
	UINT i;
	comp_error_status resp;
	prng_error_status retval = PRNG_ERR_LOW_MEMORY;
	MMPTR	mmp;
	PRNG	*p;

	mmInit();

	#if	MUTEX_ENABLE
	/* Create the mutex */
	/* NOTE: on return the mutex should bve held, since our caller (prngInitialize)
	 * will release it.
	 */
	if(mutexCreatorId!=0) {return PRNG_ERR_REINIT;}
	Statmutex = CreateMutex(NULL,TRUE,NULL);
	if(Statmutex == NULL) {mutexCreatorId = 0; return PRNG_ERR_MUTEX;}
	DuplicateHandle(GetCurrentProcess(),Statmutex,GetCurrentProcess(),&mutex,SYNCHRONIZE,FALSE,0);
	mutexCreatorId = GetCurrentProcessId();
	#endif	/* MUTEX_ENABLE */

	/* Assign memory */
	mmp = mmMalloc(sizeof(PRNG));
	if(mmp==MM_NULL)
	{
		goto cleanup_init;
	}
	else
	{
		p = (PRNG*)mmGetPtr(mmp);
		memset(p, 0, sizeof(PRNG));
	}

	/* Initialize Variables */
	for(i=0;i<TOTAL_SOURCES;i++)
	{
		p->poolSize[i] = 0;
		p->poolEstBits[i] = 0;
	}

#ifdef WIN_NT
	/* Setup security on the registry so that remote users cannot predict the slow pool */
	prng_set_NT_security();
#endif

	/* Initialize the secret state. */
	/* FIXME - might want to make this an option here and have the caller
	 * do it after we return....? */
	SHA1Init(&p->pool);
#if		SLOW_POLL_ENABLE
	prng_slow_init(p);	/* Does a slow poll and then calls prng_make_state(...) */
#else
	/* NULL init */
	prng_do_SHA1(&p->outstate);
	prng_make_new_state(&p->outstate, p->outstate.out);
#endif	/* SLOW_POLL_ENABLE */

	/* Initialize compression routines */
	for(i=0;i<COMP_SOURCES;i++)
	{
		resp = comp_init((p->comp_state)+i);
		if(resp!=COMP_SUCCESS) {retval = PRNG_ERR_COMPRESSION; goto cleanup_init;}
	}

	p->ready = PRNG_READY;
	*prng = (PrngRef)p;

	return PRNG_SUCCESS;

cleanup_init:
	/* Program failed on one of the mmmallocs */
	mmFree(mmp);
	mmp = MM_NULL;

	#if		MUTEX_ENABLE
	CloseHandle(Statmutex);
	Statmutex = NULL;
	mutexCreatorId = 0;
	#endif

	return retval; /* default PRNG_ERR_LOW_MEMORY */
}

/* Provide output */
prng_error_status
prngOutput(PRNG *p, BYTE *outbuf,UINT outbuflen)
{
	UINT i;
	GEN_CTX	*ctx = &p->outstate;

	CHECKSTATE(p);
	GENCHECK(p);
	PCHECK(outbuf);
	chASSERT(BACKTRACKLIMIT > 0);

	for(i=0;i<outbuflen;i++,ctx->index++,ctx->numout++)
	{
		/* Check backtracklimit */
		if(ctx->numout > BACKTRACKLIMIT)
		{
			prng_do_SHA1(ctx);
			prng_make_new_state(ctx, ctx->out);
		}
		/* Check position in IV */
		if(ctx->index>=20)
		{
			prng_do_SHA1(ctx);
		}
		/* Output data */
		outbuf[i] = (ctx->out)[ctx->index];
	}

	return PRNG_SUCCESS;
}


/* Cause the PRNG to reseed now regardless of entropy pool */
/* Should this be public? */
prng_error_status
prngForceReseed(PRNG *p, LONGLONG ticks)
{
	int i;
#ifdef WIN_NT
	FILETIME a,b,c,usertime;
#endif
	BYTE buf[64];
	BYTE dig[20];
#if	defined(macintosh) || defined(__APPLE__)
	#if		(defined(TARGET_API_MAC_OSX) || defined(KERNEL_BUILD))
		struct timeval 	tv;
		int64_t			endTime, curTime;
	#else	/* TARGET_API_MAC_CARBON */
		UnsignedWide 	uwide;		/* struct needed for Microseconds() */
		LONGLONG 		start;
		LONGLONG 		now;
	#endif
#endif

	CHECKSTATE(p);
	POOLCHECK(p);
	ZCHECK(ticks);

	/* Set up start and end times */
	#if		defined(macintosh) || defined(__APPLE__)
		#if		(defined(TARGET_API_MAC_OSX) || defined(KERNEL_BUILD))
			/* note we can't loop for more than a million microseconds */
            #ifdef KERNEL_BUILD
                microuptime (&tv);
            #else
                gettimeofday(&tv, NULL);
            #endif
			endTime = (int64_t)tv.tv_sec*1000000LL + (int64_t)tv.tv_usec + ticks;
		#else	/* TARGET_API_MAC_OSX */
			Microseconds(&uwide);
			start = UnsignedWideToUInt64(uwide);
		#endif	/* TARGET_API_xxx */
	#endif	/* macintosh */
	do
	{
		/* Do a couple of iterations between time checks */
		prngOutput(p, buf,64);
		SHA1Update(&p->pool,buf,64);
		prngOutput(p, buf,64);
		SHA1Update(&p->pool,buf,64);
		prngOutput(p, buf,64);
		SHA1Update(&p->pool,buf,64);
		prngOutput(p, buf,64);
		SHA1Update(&p->pool,buf,64);
		prngOutput(p, buf,64);
		SHA1Update(&p->pool,buf,64);

#if		defined(macintosh) || defined(__APPLE__)
	#if		defined(TARGET_API_MAC_OSX) || defined(KERNEL_BUILD)
        #ifdef TARGET_API_MAC_OSX
            gettimeofday(&tv, NULL);
        #else
            microuptime (&tv);
	    curTime = (int64_t)tv.tv_sec*1000000LL + (int64_t)tv.tv_usec;
        #endif
	} while(curTime < endTime);
	#else
		Microseconds(&uwide);
		now = UnsignedWideToUInt64(uwide);
	} while ( (now-start) < ticks) ;
	#endif
#else
	} while ( (now-start) < ticks) ;
#endif
	SHA1Final(dig,&p->pool);
	SHA1Update(&p->pool,dig,20);
	SHA1Final(dig,&p->pool);

	/* Reset secret state */
	SHA1Init(&p->pool);
	prng_make_new_state(&p->outstate,dig);

	/* Clear counter variables */
	for(i=0;i<TOTAL_SOURCES;i++)
	{
		p->poolSize[i] = 0;
		p->poolEstBits[i] = 0;
	}

	/* Cleanup memory */
	trashMemory(dig,20*sizeof(char));
	trashMemory(buf,64*sizeof(char));

	return PRNG_SUCCESS;
}


/* Input a state into the PRNG */
prng_error_status
prngProcessSeedBuffer(PRNG *p, BYTE *buf,LONGLONG ticks)
{
	CHECKSTATE(p);
	GENCHECK(p);
	PCHECK(buf);

	/* Put the data into the entropy, add some data from the unknown state, reseed */
	SHA1Update(&p->pool,buf,20);			/* Put it into the entropy pool */
	prng_do_SHA1(&p->outstate);				/* Output 20 more bytes and     */
	SHA1Update(&p->pool,p->outstate.out,20);/* add it to the pool as well.  */
	prngForceReseed(p, ticks); 				/* Do a reseed */
	return prngOutput(p, buf,20); /* Return the first 20 bytes of output in buf */
}


/* Take some "random" data and make more "random-looking" data from it */
/* note: this routine has no context, no mutex wrapper */
prng_error_status
prngStretch(BYTE *inbuf,UINT inbuflen,BYTE *outbuf,UINT outbuflen) {
	long int left,prev;
	SHA1_CTX ctx;
	BYTE dig[20];

	PCHECK(inbuf);
	PCHECK(outbuf);

	if(inbuflen >= outbuflen)
	{
		memcpy(outbuf,inbuf,outbuflen);
		return PRNG_SUCCESS;
	}
	else  /* Extend using SHA1 hash of inbuf */
	{
		SHA1Init(&ctx);
		SHA1Update(&ctx,inbuf,inbuflen);
		SHA1Final(dig,&ctx);
		for(prev=0,left=outbuflen;left>0;prev+=20,left-=20)
		{
			SHA1Update(&ctx,dig,20);
			SHA1Final(dig,&ctx);
			memcpy(outbuf+prev,dig,(left>20)?20:left);
		}
		trashMemory(dig,20*sizeof(BYTE));

		return PRNG_SUCCESS;
	}

	return PRNG_ERR_PROGRAM_FLOW;
}


/* Add entropy to the PRNG from a source */
prng_error_status
prngInput(PRNG *p, BYTE *inbuf,UINT inbuflen,UINT poolnum, __unused UINT estbits)
{
	#ifndef	YARROW_KERNEL
	comp_error_status resp;
	#endif

	CHECKSTATE(p);
	POOLCHECK(p);
	PCHECK(inbuf);
	if(poolnum >= TOTAL_SOURCES) {return PRNG_ERR_OUT_OF_BOUNDS;}

	/* Add to entropy pool */
	SHA1Update(&p->pool,inbuf,inbuflen);

	#ifndef	YARROW_KERNEL
	/* skip this step for the kernel */

	/* Update pool size, pool user estimate and pool compression context */
	p->poolSize[poolnum] += inbuflen;
	p->poolEstBits[poolnum] += estbits;
	if(poolnum<COMP_SOURCES)
	{
		resp = comp_add_data((p->comp_state)+poolnum,inbuf,inbuflen);
		if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
	}
	#endif	/* YARROW_KERNEL */

	return PRNG_SUCCESS;
}


/* If we have enough entropy, allow a reseed of the system */
prng_error_status
prngAllowReseed(PRNG *p, LONGLONG ticks)
{
	UINT temp[TOTAL_SOURCES];
	LONG i;
	UINT sum;
#ifndef KERNEL_BUILD
	float ratio;
#endif

#ifndef KERNEL_BUILD
	comp_error_status resp;
#endif

	CHECKSTATE(p);

	for(i=0;i<ENTROPY_SOURCES;i++)
	{
		/* Make sure that compression-based entropy estimates are current */
#ifndef KERNEL_BUILD // floating point in a kernel is BAD!
		resp = comp_get_ratio((p->comp_state)+i,&ratio);
		if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
		/* Use 4 instead of 8 to half compression estimate */
		temp[i] = (int)(ratio*p->poolSize[i]*4);
#else
        temp[i] = p->poolSize[i] * 4;
#endif

	}
	/* Use minumum of user and compression estimate for compressed sources */
	for(i=ENTROPY_SOURCES;i<COMP_SOURCES;i++)
	{
#ifndef KERNEL_BUILD
		/* Make sure that compression-based entropy estimates are current */
		resp = comp_get_ratio((p->comp_state)+i,&ratio);
		if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
		/* Use 4 instead of 8 to half compression estimate */
		temp[i] = _MIN((int)(ratio*p->poolSize[i]*4),(int)p->poolEstBits[i]);
#else
        temp[i] = _MIN (p->poolSize[i] * 4, p->poolEstBits[i]);
#endif

	}
	/* Use user estimate for remaining sources */
	for(i=COMP_SOURCES;i<TOTAL_SOURCES;i++) {temp[i] = p->poolEstBits[i];}

	if(K > 0) {
		/* pointless if we're not ignoring any sources */
		bubbleSort(temp,TOTAL_SOURCES);
	}
	for(i=K,sum=0;i<TOTAL_SOURCES;sum+=temp[i++]); /* Stupid C trick */
	if(sum>THRESHOLD)
		return prngForceReseed(p, ticks);
	else
		return PRNG_ERR_NOT_ENOUGH_ENTROPY;

	return PRNG_ERR_PROGRAM_FLOW;
}

#if		SLOW_POLL_ENABLE
/* Call a slow poll and insert the data into the entropy pool */
static prng_error_status
prngSlowPoll(PRNG *p, UINT pollsize)
{
	BYTE *buf;
	DWORD len;
	prng_error_status retval;

	CHECKSTATE(p);

	buf = (BYTE*)malloc(pollsize);
	if(buf==NULL) {return PRNG_ERR_LOW_MEMORY;}
	len = prng_slow_poll(buf,pollsize);	/* OS specific call */
	retval = prngInput(p, buf,len,SLOWPOLLSOURCE, len * 8);
	trashMemory(buf,pollsize);
	free(buf);

	return retval;
}
#endif	/* SLOW_POLL_ENABLE */


/* Delete the PRNG */
prng_error_status
prngDestroy(PRNG *p)
{
	UINT i;

	#if	MUTEX_ENABLE
	if(GetCurrentProcessId()!=mutexCreatorId) {return PRNG_ERR_WRONG_CALLER;}
	#endif
	if(p==NULL) {return PRNG_SUCCESS;} /* Well, there is nothing to destroy... */

	p->ready = PRNG_NOT_READY;

	for(i=0;i<COMP_SOURCES;i++)
	{
		comp_end((p->comp_state)+i);
	}

	#if	MUTEX_ENABLE
	CloseHandle(Statmutex);
	Statmutex = NULL;
	mutexCreatorId = 0;
	#endif

	return PRNG_SUCCESS;
}
Commit	Line	Data
	1	/*
	2	* Copyright (c) 1999, 2000-2001 Apple Computer, Inc. All rights reserved.
	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
	6	* The contents of this file constitute Original Code as defined in and
	7	* are subject to the Apple Public Source License Version 1.1 (the
	8	* "License"). You may not use this file except in compliance with the
	9	* License. Please obtain a copy of the License at
	10	* http://www.apple.com/publicsource and read it before using this file.
	11	*
	12	* This Original Code and all software distributed under the License are
	13	* distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	14	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	15	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	16	* FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
	17	* License for the specific language governing rights and limitations
	18	* under the License.
	19	*
	20	* @APPLE_LICENSE_HEADER_END@
	21	*/
	22
	23	/*
	24	File: prng.c
	25
	26	Contains: Core routines for the Counterpane Yarrow PRNG.
	27
	28	Written by: Counterpane, Inc.
	29
	30	Copyright: (c) 2000 by Apple Computer, Inc., all rights reserved.
	31
	32	Change History (most recent first):
	33
	34	02/10/99 dpm Created, based on Counterpane source.
	35
	36	*/
	37	/*
	38	prng.c
	39
	40	Core routines for the Counterpane PRNG
	41	*/
	42	#include "userdefines.h"
	43	#include "assertverify.h"
	44	#include "dev/random/YarrowCoreLib/include/yarrowUtils.h"
	45
	46	#if defined(macintosh) \|\| defined(__APPLE__)
	47	/* FIXME - this file needs to be in a platform-independent place */
	48
	49	#include "macOnly.h"
	50	#endif /* macintosh */
	51	#include "smf.h"
	52	#include "sha1mod.h"
	53	#include "entropysources.h"
	54	#include "comp.h"
	55	#include "dev/random/YarrowCoreLib/include/yarrow.h"
	56	#include "prng.h"
	57	#include "prngpriv.h"
	58
	59
	60	#define _MAX(a,b) (((a)>(b))?(a):(b))
	61	#define _MIN(a,b) (((a)<(b))?(a):(b))
	62
	63	#if defined(macintosh) \|\| defined(__APPLE__)
	64	/*
	65	* No mutexes in this module for Macintosh/OSX. We handle the
	66	* required locking elsewhere.
	67	*/
	68	#define MUTEX_ENABLE 0
	69
	70	#include <string.h> /* memcpy, etc. */
	71	#if TARGET_API_MAC_OSX
	72	#include <sys/time.h> /* for timespec */
	73	#elif TARGET_API_MAC_CARBON
	74	#include <Timer.h> /* Microseconds */
	75	#include <Math64.h>
	76	#elif KERNEL_BUILD
	77	#include <sys/time.h>
	78	#else
	79	#error Unknown TARGET_API
	80	#endif /* TARGET_API */
	81	#else
	82	#define MUTEX_ENABLE 1
	83	#endif /* macintosh */
	84
	85	#if MUTEX_ENABLE
	86	static HANDLE Statmutex = NULL;
	87	static DWORD mutexCreatorId = 0;
	88	#endif
	89
	90	#pragma mark -
	91	#pragma mark * * * Static Utility functions * * *
	92
	93	/* All error checking should be done in the function that calls these */
	94
	95	/*
	96	* out := SHA1(IV \| out)
	97	*/
	98	static void
	99	prng_do_SHA1(GEN_CTX *ctx)
	100	{
	101	SHA1_CTX sha;
	102
	103	SHA1Init(&sha);
	104	SHA1Update(&sha,ctx->IV,20);
	105	SHA1Update(&sha,ctx->out,20);
	106	SHA1Final(ctx->out,&sha);
	107	ctx->index = 0;
	108	}
	109
	110	/*
	111	* IV := newState
	112	* out := SHA1(IV)
	113	*
	114	* Called from init, prngForceReseed(), and prngOutput()
	115	* as anti-backtracking mechanism.
	116	*/
	117	static void
	118	prng_make_new_state(GEN_CTX ctx,BYTE newState)
	119	{
	120	SHA1_CTX sha;
	121
	122	memcpy(ctx->IV,newState,20);
	123	SHA1Init(&sha);
	124	SHA1Update(&sha,ctx->IV,20);
	125	SHA1Final(ctx->out,&sha);
	126	ctx->numout = 0;
	127	ctx->index = 0;
	128	}
	129
	130	#if SLOW_POLL_ENABLE
	131
	132
	133	/* Initialize the secret state with a slow poll */
	134	/* Currently only called from prngInitialize */
	135
	136	#define SPLEN 65536 /* 64K */
	137
	138	static void
	139	prng_slow_init(PRNG *p)
	140	/* This fails silently and must be fixed. */
	141	{
	142	SHA1_CTX* ctx = NULL;
	143	MMPTR mmctx = MM_NULL;
	144	BYTE* bigbuf = NULL;
	145	MMPTR mmbigbuf = MM_NULL;
	146	BYTE* buf = NULL;
	147	MMPTR mmbuf = MM_NULL;
	148	DWORD polllength;
	149
	150	mmbigbuf = mmMalloc(SPLEN);
	151	if(mmbigbuf == MM_NULL) {goto cleanup_slow_init;}
	152	bigbuf = (BYTE*)mmGetPtr(mmbigbuf);
	153
	154	mmbuf = mmMalloc(20);
	155	if(mmbuf == MM_NULL) {goto cleanup_slow_init;}
	156	buf = (BYTE*)mmGetPtr(mmbuf);
	157
	158	mmctx = mmMalloc(sizeof(SHA1_CTX));
	159	if(mmctx == MM_NULL) {goto cleanup_slow_init;}
	160	ctx = (SHA1_CTX*)mmGetPtr(mmctx);
	161
	162
	163	/* Initialize the secret state. */
	164	/* Init entropy pool */
	165	SHA1Init(&p->pool);
	166	/* Init output generator */
	167	polllength = prng_slow_poll(bigbuf,SPLEN);
	168	SHA1Init(ctx);
	169	SHA1Update(ctx,bigbuf,polllength);
	170	SHA1Final(buf,ctx);
	171	prng_make_new_state(&p->outstate, buf);
	172
	173	cleanup_slow_init:
	174	mmFree(mmctx);
	175	mmFree(mmbigbuf);
	176	mmFree(mmbuf);
	177
	178	return;
	179	}
	180
	181	#endif /* SLOW_POLL_ENABLE */
	182
	183	/* In-place modifed bubble sort */
	184	static void
	185	bubbleSort( UINT *data, LONG len )
	186	{
	187	LONG i,last,newlast;
	188	UINT temp;
	189
	190	last = len-1;
	191	while(last!=-1)
	192	{
	193	newlast = -1;
	194	for(i=0;i<last;i++)
	195	{
	196	if(data[i+1] > data[i])
	197	{
	198	newlast = i;
	199	temp = data[i];
	200	data[i] = data[i+1];
	201	data[i+1] = temp;
	202	}
	203	}
	204	last = newlast;
	205	}
	206	}
	207
	208	#pragma mark -
	209	#pragma mark * * * Public functions * * *
	210
	211	/* Set up the PRNG */
	212	prng_error_status
	213	prngInitialize(PrngRef *prng)
	214	{
	215	UINT i;
	216	comp_error_status resp;
	217	prng_error_status retval = PRNG_ERR_LOW_MEMORY;
	218	MMPTR mmp;
	219	PRNG *p;
	220
	221	mmInit();
	222
	223	#if MUTEX_ENABLE
	224	/* Create the mutex */
	225	/* NOTE: on return the mutex should bve held, since our caller (prngInitialize)
	226	* will release it.
	227	*/
	228	if(mutexCreatorId!=0) {return PRNG_ERR_REINIT;}
	229	Statmutex = CreateMutex(NULL,TRUE,NULL);
	230	if(Statmutex == NULL) {mutexCreatorId = 0; return PRNG_ERR_MUTEX;}
	231	DuplicateHandle(GetCurrentProcess(),Statmutex,GetCurrentProcess(),&mutex,SYNCHRONIZE,FALSE,0);
	232	mutexCreatorId = GetCurrentProcessId();
	233	#endif /* MUTEX_ENABLE */
	234
	235	/* Assign memory */
	236	mmp = mmMalloc(sizeof(PRNG));
	237	if(mmp==MM_NULL)
	238	{
	239	goto cleanup_init;
	240	}
	241	else
	242	{
	243	p = (PRNG*)mmGetPtr(mmp);
	244	memset(p, 0, sizeof(PRNG));
	245	}
	246
	247	/* Initialize Variables */
	248	for(i=0;i<TOTAL_SOURCES;i++)
	249	{
	250	p->poolSize[i] = 0;
	251	p->poolEstBits[i] = 0;
	252	}
	253
	254	#ifdef WIN_NT
	255	/* Setup security on the registry so that remote users cannot predict the slow pool */
	256	prng_set_NT_security();
	257	#endif
	258
	259	/* Initialize the secret state. */
	260	/* FIXME - might want to make this an option here and have the caller
	261	* do it after we return....? */
	262	SHA1Init(&p->pool);
	263	#if SLOW_POLL_ENABLE
	264	prng_slow_init(p); /* Does a slow poll and then calls prng_make_state(...) */
	265	#else
	266	/* NULL init */
	267	prng_do_SHA1(&p->outstate);
	268	prng_make_new_state(&p->outstate, p->outstate.out);
	269	#endif /* SLOW_POLL_ENABLE */
	270
	271	/* Initialize compression routines */
	272	for(i=0;i<COMP_SOURCES;i++)
	273	{
	274	resp = comp_init((p->comp_state)+i);
	275	if(resp!=COMP_SUCCESS) {retval = PRNG_ERR_COMPRESSION; goto cleanup_init;}
	276	}
	277
	278	p->ready = PRNG_READY;
	279	*prng = (PrngRef)p;
	280
	281	return PRNG_SUCCESS;
	282
	283	cleanup_init:
	284	/* Program failed on one of the mmmallocs */
	285	mmFree(mmp);
	286	mmp = MM_NULL;
	287
	288	#if MUTEX_ENABLE
	289	CloseHandle(Statmutex);
	290	Statmutex = NULL;
	291	mutexCreatorId = 0;
	292	#endif
	293
	294	return retval; /* default PRNG_ERR_LOW_MEMORY */
	295	}
	296
	297	/* Provide output */
	298	prng_error_status
	299	prngOutput(PRNG p, BYTE outbuf,UINT outbuflen)
	300	{
	301	UINT i;
	302	GEN_CTX *ctx = &p->outstate;
	303
	304	CHECKSTATE(p);
	305	GENCHECK(p);
	306	PCHECK(outbuf);
	307	chASSERT(BACKTRACKLIMIT > 0);
	308
	309	for(i=0;i<outbuflen;i++,ctx->index++,ctx->numout++)
	310	{
	311	/* Check backtracklimit */
	312	if(ctx->numout > BACKTRACKLIMIT)
	313	{
	314	prng_do_SHA1(ctx);
	315	prng_make_new_state(ctx, ctx->out);
	316	}
	317	/* Check position in IV */
	318	if(ctx->index>=20)
	319	{
	320	prng_do_SHA1(ctx);
	321	}
	322	/* Output data */
	323	outbuf[i] = (ctx->out)[ctx->index];
	324	}
	325
	326	return PRNG_SUCCESS;
	327	}
	328
	329
	330	/* Cause the PRNG to reseed now regardless of entropy pool */
	331	/* Should this be public? */
	332	prng_error_status
	333	prngForceReseed(PRNG *p, LONGLONG ticks)
	334	{
	335	int i;
	336	#ifdef WIN_NT
	337	FILETIME a,b,c,usertime;
	338	#endif
	339	BYTE buf[64];
	340	BYTE dig[20];
	341	#if defined(macintosh) \|\| defined(__APPLE__)
	342	#if (defined(TARGET_API_MAC_OSX) \|\| defined(KERNEL_BUILD))
	343	struct timeval tv;
	344	int64_t endTime, curTime;
	345	#else /* TARGET_API_MAC_CARBON */
	346	UnsignedWide uwide; /* struct needed for Microseconds() */
	347	LONGLONG start;
	348	LONGLONG now;
	349	#endif
	350	#endif
	351
	352	CHECKSTATE(p);
	353	POOLCHECK(p);
	354	ZCHECK(ticks);
	355
	356	/* Set up start and end times */
	357	#if defined(macintosh) \|\| defined(__APPLE__)
	358	#if (defined(TARGET_API_MAC_OSX) \|\| defined(KERNEL_BUILD))
	359	/* note we can't loop for more than a million microseconds */
	360	#ifdef KERNEL_BUILD
	361	microuptime (&tv);
	362	#else
	363	gettimeofday(&tv, NULL);
	364	#endif
	365	endTime = (int64_t)tv.tv_sec*1000000LL + (int64_t)tv.tv_usec + ticks;
	366	#else /* TARGET_API_MAC_OSX */
	367	Microseconds(&uwide);
	368	start = UnsignedWideToUInt64(uwide);
	369	#endif /* TARGET_API_xxx */
	370	#endif /* macintosh */
	371	do
	372	{
	373	/* Do a couple of iterations between time checks */
	374	prngOutput(p, buf,64);
	375	SHA1Update(&p->pool,buf,64);
	376	prngOutput(p, buf,64);
	377	SHA1Update(&p->pool,buf,64);
	378	prngOutput(p, buf,64);
	379	SHA1Update(&p->pool,buf,64);
	380	prngOutput(p, buf,64);
	381	SHA1Update(&p->pool,buf,64);
	382	prngOutput(p, buf,64);
	383	SHA1Update(&p->pool,buf,64);
	384
	385	#if defined(macintosh) \|\| defined(__APPLE__)
	386	#if defined(TARGET_API_MAC_OSX) \|\| defined(KERNEL_BUILD)
	387	#ifdef TARGET_API_MAC_OSX
	388	gettimeofday(&tv, NULL);
	389	#else
	390	microuptime (&tv);
	391	curTime = (int64_t)tv.tv_sec*1000000LL + (int64_t)tv.tv_usec;
	392	#endif
	393	} while(curTime < endTime);
	394	#else
	395	Microseconds(&uwide);
	396	now = UnsignedWideToUInt64(uwide);
	397	} while ( (now-start) < ticks) ;
	398	#endif
	399	#else
	400	} while ( (now-start) < ticks) ;
	401	#endif
	402	SHA1Final(dig,&p->pool);
	403	SHA1Update(&p->pool,dig,20);
	404	SHA1Final(dig,&p->pool);
	405
	406	/* Reset secret state */
	407	SHA1Init(&p->pool);
	408	prng_make_new_state(&p->outstate,dig);
	409
	410	/* Clear counter variables */
	411	for(i=0;i<TOTAL_SOURCES;i++)
	412	{
	413	p->poolSize[i] = 0;
	414	p->poolEstBits[i] = 0;
	415	}
	416
	417	/* Cleanup memory */
	418	trashMemory(dig,20*sizeof(char));
	419	trashMemory(buf,64*sizeof(char));
	420
	421	return PRNG_SUCCESS;
	422	}
	423
	424
	425	/* Input a state into the PRNG */
	426	prng_error_status
	427	prngProcessSeedBuffer(PRNG p, BYTE buf,LONGLONG ticks)
	428	{
	429	CHECKSTATE(p);
	430	GENCHECK(p);
	431	PCHECK(buf);
	432
	433	/* Put the data into the entropy, add some data from the unknown state, reseed */
	434	SHA1Update(&p->pool,buf,20); /* Put it into the entropy pool */
	435	prng_do_SHA1(&p->outstate); /* Output 20 more bytes and */
	436	SHA1Update(&p->pool,p->outstate.out,20);/* add it to the pool as well. */
	437	prngForceReseed(p, ticks); /* Do a reseed */
	438	return prngOutput(p, buf,20); /* Return the first 20 bytes of output in buf */
	439	}
	440
	441
	442	/* Take some "random" data and make more "random-looking" data from it */
	443	/* note: this routine has no context, no mutex wrapper */
	444	prng_error_status
	445	prngStretch(BYTE inbuf,UINT inbuflen,BYTE outbuf,UINT outbuflen) {
	446	long int left,prev;
	447	SHA1_CTX ctx;
	448	BYTE dig[20];
	449
	450	PCHECK(inbuf);
	451	PCHECK(outbuf);
	452
	453	if(inbuflen >= outbuflen)
	454	{
	455	memcpy(outbuf,inbuf,outbuflen);
	456	return PRNG_SUCCESS;
	457	}
	458	else /* Extend using SHA1 hash of inbuf */
	459	{
	460	SHA1Init(&ctx);
	461	SHA1Update(&ctx,inbuf,inbuflen);
	462	SHA1Final(dig,&ctx);
	463	for(prev=0,left=outbuflen;left>0;prev+=20,left-=20)
	464	{
	465	SHA1Update(&ctx,dig,20);
	466	SHA1Final(dig,&ctx);
	467	memcpy(outbuf+prev,dig,(left>20)?20:left);
	468	}
	469	trashMemory(dig,20*sizeof(BYTE));
	470
	471	return PRNG_SUCCESS;
	472	}
	473
	474	return PRNG_ERR_PROGRAM_FLOW;
	475	}
	476
	477
	478	/* Add entropy to the PRNG from a source */
	479	prng_error_status
	480	prngInput(PRNG p, BYTE inbuf,UINT inbuflen,UINT poolnum, __unused UINT estbits)
	481	{
	482	#ifndef YARROW_KERNEL
	483	comp_error_status resp;
	484	#endif
	485
	486	CHECKSTATE(p);
	487	POOLCHECK(p);
	488	PCHECK(inbuf);
	489	if(poolnum >= TOTAL_SOURCES) {return PRNG_ERR_OUT_OF_BOUNDS;}
	490
	491	/* Add to entropy pool */
	492	SHA1Update(&p->pool,inbuf,inbuflen);
	493
	494	#ifndef YARROW_KERNEL
	495	/* skip this step for the kernel */
	496
	497	/* Update pool size, pool user estimate and pool compression context */
	498	p->poolSize[poolnum] += inbuflen;
	499	p->poolEstBits[poolnum] += estbits;
	500	if(poolnum<COMP_SOURCES)
	501	{
	502	resp = comp_add_data((p->comp_state)+poolnum,inbuf,inbuflen);
	503	if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
	504	}
	505	#endif /* YARROW_KERNEL */
	506
	507	return PRNG_SUCCESS;
	508	}
	509
	510
	511
	512	/* If we have enough entropy, allow a reseed of the system */
	513	prng_error_status
	514	prngAllowReseed(PRNG *p, LONGLONG ticks)
	515	{
	516	UINT temp[TOTAL_SOURCES];
	517	LONG i;
	518	UINT sum;
	519	#ifndef KERNEL_BUILD
	520	float ratio;
	521	#endif
	522
	523	#ifndef KERNEL_BUILD
	524	comp_error_status resp;
	525	#endif
	526
	527	CHECKSTATE(p);
	528
	529	for(i=0;i<ENTROPY_SOURCES;i++)
	530	{
	531	/* Make sure that compression-based entropy estimates are current */
	532	#ifndef KERNEL_BUILD // floating point in a kernel is BAD!
	533	resp = comp_get_ratio((p->comp_state)+i,&ratio);
	534	if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
	535	/* Use 4 instead of 8 to half compression estimate */
	536	temp[i] = (int)(ratiop->poolSize[i]4);
	537	#else
	538	temp[i] = p->poolSize[i] * 4;
	539	#endif
	540
	541	}
	542	/* Use minumum of user and compression estimate for compressed sources */
	543	for(i=ENTROPY_SOURCES;i<COMP_SOURCES;i++)
	544	{
	545	#ifndef KERNEL_BUILD
	546	/* Make sure that compression-based entropy estimates are current */
	547	resp = comp_get_ratio((p->comp_state)+i,&ratio);
	548	if(resp!=COMP_SUCCESS) {return PRNG_ERR_COMPRESSION;}
	549	/* Use 4 instead of 8 to half compression estimate */
	550	temp[i] = _MIN((int)(ratiop->poolSize[i]4),(int)p->poolEstBits[i]);
	551	#else
	552	temp[i] = _MIN (p->poolSize[i] * 4, p->poolEstBits[i]);
	553	#endif
	554
	555	}
	556	/* Use user estimate for remaining sources */
	557	for(i=COMP_SOURCES;i<TOTAL_SOURCES;i++) {temp[i] = p->poolEstBits[i];}
	558
	559	if(K > 0) {
	560	/* pointless if we're not ignoring any sources */
	561	bubbleSort(temp,TOTAL_SOURCES);
	562	}
	563	for(i=K,sum=0;i<TOTAL_SOURCES;sum+=temp[i++]); /* Stupid C trick */
	564	if(sum>THRESHOLD)
	565	return prngForceReseed(p, ticks);
	566	else
	567	return PRNG_ERR_NOT_ENOUGH_ENTROPY;
	568
	569	return PRNG_ERR_PROGRAM_FLOW;
	570	}
	571
	572	#if SLOW_POLL_ENABLE
	573	/* Call a slow poll and insert the data into the entropy pool */
	574	static prng_error_status
	575	prngSlowPoll(PRNG *p, UINT pollsize)
	576	{
	577	BYTE *buf;
	578	DWORD len;
	579	prng_error_status retval;
	580
	581	CHECKSTATE(p);
	582
	583	buf = (BYTE*)malloc(pollsize);
	584	if(buf==NULL) {return PRNG_ERR_LOW_MEMORY;}
	585	len = prng_slow_poll(buf,pollsize); /* OS specific call */
	586	retval = prngInput(p, buf,len,SLOWPOLLSOURCE, len * 8);
	587	trashMemory(buf,pollsize);
	588	free(buf);
	589
	590	return retval;
	591	}
	592	#endif /* SLOW_POLL_ENABLE */
	593
	594
	595	/* Delete the PRNG */
	596	prng_error_status
	597	prngDestroy(PRNG *p)
	598	{
	599	UINT i;
	600
	601	#if MUTEX_ENABLE
	602	if(GetCurrentProcessId()!=mutexCreatorId) {return PRNG_ERR_WRONG_CALLER;}
	603	#endif
	604	if(p==NULL) {return PRNG_SUCCESS;} /* Well, there is nothing to destroy... */
	605
	606	p->ready = PRNG_NOT_READY;
	607
	608	for(i=0;i<COMP_SOURCES;i++)
	609	{
	610	comp_end((p->comp_state)+i);
	611	}
	612
	613	#if MUTEX_ENABLE
	614	CloseHandle(Statmutex);
	615	Statmutex = NULL;
	616	mutexCreatorId = 0;
	617	#endif
	618
	619	return PRNG_SUCCESS;
	620	}
	621
	622