2 * Copyright (c) 1999, 2000-2001 Apple Computer, Inc. All rights reserved.
4 * @APPLE_LICENSE_HEADER_START@
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.
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
20 * @APPLE_LICENSE_HEADER_END@
26 Contains: Core routines for the Counterpane Yarrow PRNG.
28 Written by: Counterpane, Inc.
30 Copyright: (c) 2000 by Apple Computer, Inc., all rights reserved.
32 Change History (most recent first):
34 02/10/99 dpm Created, based on Counterpane source.
40 Core routines for the Counterpane PRNG
42 #include "userdefines.h"
43 #include "assertverify.h"
44 #include "dev/random/YarrowCoreLib/include/yarrowUtils.h"
46 #if defined(macintosh) || defined(__APPLE__)
47 /* FIXME - this file needs to be in a platform-independent place */
50 #endif /* macintosh */
53 #include "entropysources.h"
55 #include "dev/random/YarrowCoreLib/include/yarrow.h"
60 #define _MAX(a,b) (((a)>(b))?(a):(b))
61 #define _MIN(a,b) (((a)<(b))?(a):(b))
63 #if defined(macintosh) || defined(__APPLE__)
65 * No mutexes in this module for Macintosh/OSX. We handle the
66 * required locking elsewhere.
68 #define MUTEX_ENABLE 0
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 */
79 #error Unknown TARGET_API
80 #endif /* TARGET_API */
82 #define MUTEX_ENABLE 1
83 #endif /* macintosh */
86 static HANDLE Statmutex
= NULL
;
87 static DWORD mutexCreatorId
= 0;
91 #pragma mark * * * Static Utility functions * * *
93 /* All error checking should be done in the function that calls these */
96 * out := SHA1(IV | out)
99 prng_do_SHA1(GEN_CTX
*ctx
)
104 SHA1Update(&sha
,ctx
->IV
,20);
105 SHA1Update(&sha
,ctx
->out
,20);
106 SHA1Final(ctx
->out
,&sha
);
114 * Called from init, prngForceReseed(), and prngOutput()
115 * as anti-backtracking mechanism.
118 prng_make_new_state(GEN_CTX
*ctx
,BYTE
*newState
)
122 memcpy(ctx
->IV
,newState
,20);
124 SHA1Update(&sha
,ctx
->IV
,20);
125 SHA1Final(ctx
->out
,&sha
);
133 /* Initialize the secret state with a slow poll */
134 /* Currently only called from prngInitialize */
136 #define SPLEN 65536 /* 64K */
139 prng_slow_init(PRNG
*p
)
140 /* This fails silently and must be fixed. */
142 SHA1_CTX
* ctx
= NULL
;
143 MMPTR mmctx
= MM_NULL
;
145 MMPTR mmbigbuf
= MM_NULL
;
147 MMPTR mmbuf
= MM_NULL
;
150 mmbigbuf
= mmMalloc(SPLEN
);
151 if(mmbigbuf
== MM_NULL
) {goto cleanup_slow_init
;}
152 bigbuf
= (BYTE
*)mmGetPtr(mmbigbuf
);
154 mmbuf
= mmMalloc(20);
155 if(mmbuf
== MM_NULL
) {goto cleanup_slow_init
;}
156 buf
= (BYTE
*)mmGetPtr(mmbuf
);
158 mmctx
= mmMalloc(sizeof(SHA1_CTX
));
159 if(mmctx
== MM_NULL
) {goto cleanup_slow_init
;}
160 ctx
= (SHA1_CTX
*)mmGetPtr(mmctx
);
163 /* Initialize the secret state. */
164 /* Init entropy pool */
166 /* Init output generator */
167 polllength
= prng_slow_poll(bigbuf
,SPLEN
);
169 SHA1Update(ctx
,bigbuf
,polllength
);
171 prng_make_new_state(&p
->outstate
, buf
);
181 #endif /* SLOW_POLL_ENABLE */
183 /* In-place modifed bubble sort */
185 bubbleSort( UINT
*data
, LONG len
)
196 if(data
[i
+1] > data
[i
])
209 #pragma mark * * * Public functions * * *
211 /* Set up the PRNG */
213 prngInitialize(PrngRef
*prng
)
216 comp_error_status resp
;
217 prng_error_status retval
= PRNG_ERR_LOW_MEMORY
;
224 /* Create the mutex */
225 /* NOTE: on return the mutex should bve held, since our caller (prngInitialize)
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 */
236 mmp
= mmMalloc(sizeof(PRNG
));
243 p
= (PRNG
*)mmGetPtr(mmp
);
244 memset(p
, 0, sizeof(PRNG
));
247 /* Initialize Variables */
248 for(i
=0;i
<TOTAL_SOURCES
;i
++)
251 p
->poolEstBits
[i
] = 0;
255 /* Setup security on the registry so that remote users cannot predict the slow pool */
256 prng_set_NT_security();
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....? */
264 prng_slow_init(p
); /* Does a slow poll and then calls prng_make_state(...) */
267 prng_do_SHA1(&p
->outstate
);
268 prng_make_new_state(&p
->outstate
, p
->outstate
.out
);
269 #endif /* SLOW_POLL_ENABLE */
271 /* Initialize compression routines */
272 for(i
=0;i
<COMP_SOURCES
;i
++)
274 resp
= comp_init((p
->comp_state
)+i
);
275 if(resp
!=COMP_SUCCESS
) {retval
= PRNG_ERR_COMPRESSION
; goto cleanup_init
;}
278 p
->ready
= PRNG_READY
;
284 /* Program failed on one of the mmmallocs */
289 CloseHandle(Statmutex
);
294 return retval
; /* default PRNG_ERR_LOW_MEMORY */
299 prngOutput(PRNG
*p
, BYTE
*outbuf
,UINT outbuflen
)
302 GEN_CTX
*ctx
= &p
->outstate
;
307 chASSERT(BACKTRACKLIMIT
> 0);
309 for(i
=0;i
<outbuflen
;i
++,ctx
->index
++,ctx
->numout
++)
311 /* Check backtracklimit */
312 if(ctx
->numout
> BACKTRACKLIMIT
)
315 prng_make_new_state(ctx
, ctx
->out
);
317 /* Check position in IV */
323 outbuf
[i
] = (ctx
->out
)[ctx
->index
];
330 /* Cause the PRNG to reseed now regardless of entropy pool */
331 /* Should this be public? */
333 prngForceReseed(PRNG
*p
, LONGLONG ticks
)
337 FILETIME a
,b
,c
,usertime
;
341 #if defined(macintosh) || defined(__APPLE__)
342 #if (defined(TARGET_API_MAC_OSX) || defined(KERNEL_BUILD))
344 int64_t endTime
, curTime
;
345 #else /* TARGET_API_MAC_CARBON */
346 UnsignedWide uwide
; /* struct needed for Microseconds() */
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 */
363 gettimeofday(&tv
, NULL
);
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 */
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);
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
);
391 curTime
= (int64_t)tv
.tv_sec
*1000000LL + (int64_t)tv
.tv_usec
;
393 } while(curTime
< endTime
);
395 Microseconds(&uwide
);
396 now
= UnsignedWideToUInt64(uwide
);
397 } while ( (now
-start
) < ticks
) ;
400 } while ( (now
-start
) < ticks
) ;
402 SHA1Final(dig
,&p
->pool
);
403 SHA1Update(&p
->pool
,dig
,20);
404 SHA1Final(dig
,&p
->pool
);
406 /* Reset secret state */
408 prng_make_new_state(&p
->outstate
,dig
);
410 /* Clear counter variables */
411 for(i
=0;i
<TOTAL_SOURCES
;i
++)
414 p
->poolEstBits
[i
] = 0;
418 trashMemory(dig
,20*sizeof(char));
419 trashMemory(buf
,64*sizeof(char));
425 /* Input a state into the PRNG */
427 prngProcessSeedBuffer(PRNG
*p
, BYTE
*buf
,LONGLONG ticks
)
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 */
442 /* Take some "random" data and make more "random-looking" data from it */
443 /* note: this routine has no context, no mutex wrapper */
445 prngStretch(BYTE
*inbuf
,UINT inbuflen
,BYTE
*outbuf
,UINT outbuflen
) {
453 if(inbuflen
>= outbuflen
)
455 memcpy(outbuf
,inbuf
,outbuflen
);
458 else /* Extend using SHA1 hash of inbuf */
461 SHA1Update(&ctx
,inbuf
,inbuflen
);
463 for(prev
=0,left
=outbuflen
;left
>0;prev
+=20,left
-=20)
465 SHA1Update(&ctx
,dig
,20);
467 memcpy(outbuf
+prev
,dig
,(left
>20)?20:left
);
469 trashMemory(dig
,20*sizeof(BYTE
));
474 return PRNG_ERR_PROGRAM_FLOW
;
478 /* Add entropy to the PRNG from a source */
480 prngInput(PRNG
*p
, BYTE
*inbuf
,UINT inbuflen
,UINT poolnum
, __unused UINT estbits
)
482 #ifndef YARROW_KERNEL
483 comp_error_status resp
;
489 if(poolnum
>= TOTAL_SOURCES
) {return PRNG_ERR_OUT_OF_BOUNDS
;}
491 /* Add to entropy pool */
492 SHA1Update(&p
->pool
,inbuf
,inbuflen
);
494 #ifndef YARROW_KERNEL
495 /* skip this step for the kernel */
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
)
502 resp
= comp_add_data((p
->comp_state
)+poolnum
,inbuf
,inbuflen
);
503 if(resp
!=COMP_SUCCESS
) {return PRNG_ERR_COMPRESSION
;}
505 #endif /* YARROW_KERNEL */
512 /* If we have enough entropy, allow a reseed of the system */
514 prngAllowReseed(PRNG
*p
, LONGLONG ticks
)
516 UINT temp
[TOTAL_SOURCES
];
524 comp_error_status resp
;
529 for(i
=0;i
<ENTROPY_SOURCES
;i
++)
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)(ratio
*p
->poolSize
[i
]*4);
538 temp
[i
] = p
->poolSize
[i
] * 4;
542 /* Use minumum of user and compression estimate for compressed sources */
543 for(i
=ENTROPY_SOURCES
;i
<COMP_SOURCES
;i
++)
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)(ratio
*p
->poolSize
[i
]*4),(int)p
->poolEstBits
[i
]);
552 temp
[i
] = _MIN (p
->poolSize
[i
] * 4, p
->poolEstBits
[i
]);
556 /* Use user estimate for remaining sources */
557 for(i
=COMP_SOURCES
;i
<TOTAL_SOURCES
;i
++) {temp
[i
] = p
->poolEstBits
[i
];}
560 /* pointless if we're not ignoring any sources */
561 bubbleSort(temp
,TOTAL_SOURCES
);
563 for(i
=K
,sum
=0;i
<TOTAL_SOURCES
;sum
+=temp
[i
++]); /* Stupid C trick */
565 return prngForceReseed(p
, ticks
);
567 return PRNG_ERR_NOT_ENOUGH_ENTROPY
;
569 return PRNG_ERR_PROGRAM_FLOW
;
573 /* Call a slow poll and insert the data into the entropy pool */
574 static prng_error_status
575 prngSlowPoll(PRNG
*p
, UINT pollsize
)
579 prng_error_status retval
;
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
);
592 #endif /* SLOW_POLL_ENABLE */
595 /* Delete the PRNG */
602 if(GetCurrentProcessId()!=mutexCreatorId
) {return PRNG_ERR_WRONG_CALLER
;}
604 if(p
==NULL
) {return PRNG_SUCCESS
;} /* Well, there is nothing to destroy... */
606 p
->ready
= PRNG_NOT_READY
;
608 for(i
=0;i
<COMP_SOURCES
;i
++)
610 comp_end((p
->comp_state
)+i
);
614 CloseHandle(Statmutex
);