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