2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
5 % RRRR AAA N N DDDD OOO M M %
6 % R R A A NN N D D O O MM MM %
7 % RRRR AAAAA N N N D D O O M M M %
8 % R R A A N NN D D O O M M %
9 % R R A A N N DDDD OOO M M %
12 % MagickCore Methods to Generate Random Numbers %
19 % Copyright 1999-2011 ImageMagick Studio LLC, a non-profit organization %
20 % dedicated to making software imaging solutions freely available. %
22 % You may not use this file except in compliance with the License. You may %
23 % obtain a copy of the License at %
25 % http://www.imagemagick.org/script/license.php %
27 % Unless required by applicable law or agreed to in writing, software %
28 % distributed under the License is distributed on an "AS IS" BASIS, %
29 % WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %
30 % See the License for the specific language governing permissions and %
31 % limitations under the License. %
33 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
35 % The generation of random numbers is too important to be left to chance.
36 % -- Tom Christiansen <tchrist@mox.perl.com>
47 #if defined(__MINGW32__)
50 #include "MagickCore/studio.h"
51 #include "MagickCore/exception.h"
52 #include "MagickCore/exception-private.h"
53 #include "MagickCore/memory_.h"
54 #include "MagickCore/semaphore.h"
55 #include "MagickCore/random_.h"
56 #include "MagickCore/random-private.h"
57 #include "MagickCore/resource_.h"
58 #include "MagickCore/signature-private.h"
59 #include "MagickCore/string_.h"
60 #include "MagickCore/thread_.h"
61 #include "MagickCore/thread-private.h"
62 #include "MagickCore/utility.h"
66 #define PseudoRandomHash SHA256Hash
67 #define RandomEntropyLevel 9
68 #define RandomFilename "reservoir.xdm"
69 #define RandomFiletype "random"
70 #define RandomProtocolMajorVersion 1
71 #define RandomProtocolMinorVersion 0
109 External declarations.
111 #if defined(__APPLE__) && !defined(TARGET_OS_IPHONE)
112 #include <crt_externs.h>
113 #define environ (*_NSGetEnviron())
123 *random_semaphore = (SemaphoreInfo *) NULL;
128 static MagickBooleanType
129 gather_true_random = MagickFalse;
132 Forward declarations.
135 *GenerateEntropicChaos(RandomInfo *);
138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
142 % A c q u i r e R a n d o m I n f o %
146 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
148 % AcquireRandomInfo() allocates the RandomInfo structure.
150 % The format of the AcquireRandomInfo method is:
152 % RandomInfo *AcquireRandomInfo(void)
156 static inline size_t MagickMin(const size_t x,const size_t y)
163 MagickExport RandomInfo *AcquireRandomInfo(void)
176 random_info=(RandomInfo *) AcquireMagickMemory(sizeof(*random_info));
177 if (random_info == (RandomInfo *) NULL)
178 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
179 (void) ResetMagickMemory(random_info,0,sizeof(*random_info));
180 random_info->signature_info=AcquireSignatureInfo();
181 random_info->nonce=AcquireStringInfo(2*GetSignatureDigestsize(
182 random_info->signature_info));
183 ResetStringInfo(random_info->nonce);
184 random_info->reservoir=AcquireStringInfo(GetSignatureDigestsize(
185 random_info->signature_info));
186 ResetStringInfo(random_info->reservoir);
187 random_info->normalize=1.0/(~0UL);
188 random_info->semaphore=AllocateSemaphoreInfo();
189 random_info->protocol_major=RandomProtocolMajorVersion;
190 random_info->protocol_minor=RandomProtocolMinorVersion;
191 random_info->timestamp=(ssize_t) time(0);
192 random_info->signature=MagickSignature;
196 nonce=GenerateEntropicChaos(random_info);
197 if (nonce == (StringInfo *) NULL)
198 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
199 InitializeSignature(random_info->signature_info);
200 UpdateSignature(random_info->signature_info,nonce);
201 FinalizeSignature(random_info->signature_info);
202 SetStringInfoLength(nonce,(GetSignatureDigestsize(
203 random_info->signature_info)+1)/2);
204 SetStringInfo(nonce,GetSignatureDigest(random_info->signature_info));
205 SetStringInfo(random_info->nonce,nonce);
206 nonce=DestroyStringInfo(nonce);
208 Seed random reservoir with entropic data.
210 entropy=GenerateEntropicChaos(random_info);
211 if (entropy == (StringInfo *) NULL)
212 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
213 UpdateSignature(random_info->signature_info,entropy);
214 FinalizeSignature(random_info->signature_info);
215 SetStringInfo(random_info->reservoir,GetSignatureDigest(
216 random_info->signature_info));
217 entropy=DestroyStringInfo(entropy);
219 Seed pseudo random number generator.
221 if (random_seed == ~0UL)
223 key=GetRandomKey(random_info,sizeof(random_seed));
224 (void) CopyMagickMemory(random_info->seed,GetStringInfoDatum(key),
225 GetStringInfoLength(key));
226 key=DestroyStringInfo(key);
233 signature_info=AcquireSignatureInfo();
234 key=AcquireStringInfo(sizeof(random_seed));
235 SetStringInfoDatum(key,(unsigned char *) &random_seed);
236 UpdateSignature(signature_info,key);
237 key=DestroyStringInfo(key);
238 FinalizeSignature(signature_info);
239 digest=GetSignatureDigest(signature_info);
240 (void) CopyMagickMemory(random_info->seed,GetStringInfoDatum(digest),
241 MagickMin(GetSignatureDigestsize(signature_info),
242 sizeof(*random_info->seed)));
243 signature_info=DestroySignatureInfo(signature_info);
245 random_info->seed[1]=0x50a7f451UL;
246 random_info->seed[2]=0x5365417eUL;
247 random_info->seed[3]=0xc3a4171aUL;
252 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
256 + D e s t r o y R a n d o m I n f o %
260 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
262 % DestroyRandomInfo() deallocates memory associated with the random
265 % The format of the DestroyRandomInfo method is:
267 % RandomInfo *DestroyRandomInfo(RandomInfo *random_info)
269 % A description of each parameter follows:
271 % o random_info: the random info.
274 MagickExport RandomInfo *DestroyRandomInfo(RandomInfo *random_info)
276 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
277 assert(random_info != (RandomInfo *) NULL);
278 assert(random_info->signature == MagickSignature);
279 LockSemaphoreInfo(random_info->semaphore);
280 if (random_info->reservoir != (StringInfo *) NULL)
281 random_info->reservoir=DestroyStringInfo(random_info->reservoir);
282 if (random_info->nonce != (StringInfo *) NULL)
283 random_info->nonce=DestroyStringInfo(random_info->nonce);
284 if (random_info->signature_info != (SignatureInfo *) NULL)
285 random_info->signature_info=DestroySignatureInfo(
286 random_info->signature_info);
287 (void) ResetMagickMemory(random_info->seed,0,sizeof(*random_info->seed));
288 random_info->signature=(~MagickSignature);
289 UnlockSemaphoreInfo(random_info->semaphore);
290 DestroySemaphoreInfo(&random_info->semaphore);
291 random_info=(RandomInfo *) RelinquishMagickMemory(random_info);
296 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
300 + G e n e r a t e E n t r o p i c C h a o s %
304 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
306 % GenerateEntropicChaos() generate entropic chaos used to initialize the
309 % The format of the GenerateEntropicChaos method is:
311 % StringInfo *GenerateEntropicChaos(RandomInfo *random_info)
313 % A description of each parameter follows:
315 % o random_info: the random info.
319 #if !defined(MAGICKCORE_WINDOWS_SUPPORT)
320 static ssize_t ReadRandom(int file,unsigned char *source,size_t length)
322 register unsigned char
330 for (q=source; length != 0; length-=count)
332 count=(ssize_t) read(file,q,length);
347 static StringInfo *GenerateEntropicChaos(RandomInfo *random_info)
349 #define MaxEntropyExtent 64
366 Initialize random reservoir.
368 entropy=AcquireStringInfo(0);
369 LockSemaphoreInfo(random_info->semaphore);
370 chaos=AcquireStringInfo(sizeof(unsigned char *));
371 SetStringInfoDatum(chaos,(unsigned char *) &entropy);
372 ConcatenateStringInfo(entropy,chaos);
373 SetStringInfoDatum(chaos,(unsigned char *) entropy);
374 ConcatenateStringInfo(entropy,chaos);
375 pid=(ssize_t) getpid();
376 SetStringInfoLength(chaos,sizeof(pid));
377 SetStringInfoDatum(chaos,(unsigned char *) &pid);
378 ConcatenateStringInfo(entropy,chaos);
379 tid=GetMagickThreadId();
380 SetStringInfoLength(chaos,sizeof(tid));
381 SetStringInfoDatum(chaos,(unsigned char *) &tid);
382 ConcatenateStringInfo(entropy,chaos);
383 #if defined(MAGICKCORE_HAVE_GETRUSAGE) && defined(RUSAGE_SELF)
388 if (getrusage(RUSAGE_SELF,&usage) == 0)
390 SetStringInfoLength(chaos,sizeof(usage));
391 SetStringInfoDatum(chaos,(unsigned char *) &usage);
395 seconds=time((time_t *) 0);
397 #if defined(MAGICKCORE_HAVE_GETTIMEOFDAY)
402 if (gettimeofday(&timer,(struct timezone *) NULL) == 0)
404 seconds=timer.tv_sec;
405 nanoseconds=1000UL*timer.tv_usec;
409 #if defined(MAGICKCORE_HAVE_CLOCK_GETTIME) && defined(CLOCK_REALTIME_HR)
414 if (clock_gettime(CLOCK_REALTIME_HR,&timer) == 0)
416 seconds=timer.tv_sec;
417 nanoseconds=timer.tv_nsec;
421 SetStringInfoLength(chaos,sizeof(seconds));
422 SetStringInfoDatum(chaos,(unsigned char *) &seconds);
423 ConcatenateStringInfo(entropy,chaos);
424 SetStringInfoLength(chaos,sizeof(nanoseconds));
425 SetStringInfoDatum(chaos,(unsigned char *) &nanoseconds);
426 ConcatenateStringInfo(entropy,chaos);
428 #if defined(MAGICKCORE_HAVE_CLOCK)
431 #if defined(MAGICKCORE_HAVE_TIMES)
436 (void) times(&timer);
437 nanoseconds=timer.tms_utime+timer.tms_stime;
440 SetStringInfoLength(chaos,sizeof(nanoseconds));
441 SetStringInfoDatum(chaos,(unsigned char *) &nanoseconds);
442 ConcatenateStringInfo(entropy,chaos);
443 #if defined(MAGICKCORE_HAVE_MKSTEMP)
451 filename=ConstantString("magickXXXXXX");
452 file=mkstemp(filename);
454 setmode(file,O_BINARY);
458 (void) remove(filename);
459 SetStringInfoLength(chaos,strlen(filename));
460 SetStringInfoDatum(chaos,(unsigned char *) filename);
461 ConcatenateStringInfo(entropy,chaos);
462 filename=DestroyString(filename);
465 #if defined(MAGICKCORE_WINDOWS_SUPPORT)
477 Not crytographically strong but better than nothing.
479 seconds=NTElapsedTime()+NTUserTime();
480 SetStringInfoLength(chaos,sizeof(seconds));
481 SetStringInfoDatum(chaos,(unsigned char *) &seconds);
482 ConcatenateStringInfo(entropy,chaos);
483 if (QueryPerformanceCounter(&nanoseconds) != 0)
485 SetStringInfoLength(chaos,sizeof(nanoseconds));
486 SetStringInfoDatum(chaos,(unsigned char *) &nanoseconds);
487 ConcatenateStringInfo(entropy,chaos);
490 Our best hope for true entropy.
492 SetStringInfoLength(chaos,MaxEntropyExtent);
493 status=NTGatherRandomData(MaxEntropyExtent,GetStringInfoDatum(chaos));
494 ConcatenateStringInfo(entropy,chaos);
511 Not crytographically strong but better than nothing.
513 if (environ != (char **) NULL)
519 Squeeze some entropy from the sometimes unpredicatble environment.
521 for (i=0; environ[i] != (char *) NULL; i++)
523 SetStringInfoLength(chaos,strlen(environ[i]));
524 SetStringInfoDatum(chaos,(unsigned char *) environ[i]);
525 ConcatenateStringInfo(entropy,chaos);
528 filename=AcquireString("/dev/urandom");
529 device=StringToStringInfo(filename);
530 device=DestroyStringInfo(device);
531 file=open(filename,O_RDONLY | O_BINARY);
532 filename=DestroyString(filename);
535 SetStringInfoLength(chaos,MaxEntropyExtent);
536 count=ReadRandom(file,GetStringInfoDatum(chaos),MaxEntropyExtent);
538 SetStringInfoLength(chaos,(size_t) count);
539 ConcatenateStringInfo(entropy,chaos);
541 if (gather_true_random != MagickFalse)
544 Our best hope for true entropy.
546 filename=AcquireString("/dev/random");
547 device=StringToStringInfo(filename);
548 device=DestroyStringInfo(device);
549 file=open(filename,O_RDONLY | O_BINARY);
550 filename=DestroyString(filename);
553 filename=AcquireString("/dev/srandom");
554 device=StringToStringInfo(filename);
555 device=DestroyStringInfo(device);
556 file=open(filename,O_RDONLY | O_BINARY);
560 SetStringInfoLength(chaos,MaxEntropyExtent);
561 count=ReadRandom(file,GetStringInfoDatum(chaos),MaxEntropyExtent);
563 SetStringInfoLength(chaos,(size_t) count);
564 ConcatenateStringInfo(entropy,chaos);
569 chaos=DestroyStringInfo(chaos);
570 UnlockSemaphoreInfo(random_info->semaphore);
575 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
579 % G e t P s e u d o R a n d o m V a l u e %
583 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
585 % GetPseudoRandomValue() return a non-negative double-precision floating-point
586 % value uniformly distributed over the interval [0.0, 1.0) with a 2 to the
589 % The format of the GetPseudoRandomValue method is:
591 % double GetPseudoRandomValue(RandomInfo *randon_info)
593 % A description of each parameter follows:
595 % o random_info: the random info.
598 MagickExport double GetPseudoRandomValue(RandomInfo *random_info)
600 register unsigned long
606 seed=random_info->seed;
609 alpha=(unsigned long) (seed[1] ^ (seed[1] << 11));
613 seed[0]=(seed[0] ^ (seed[0] >> 19)) ^ (alpha ^ (alpha >> 8));
614 } while (seed[0] == ~0UL);
615 return(random_info->normalize*seed[0]);
619 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
623 % G e t R a n d o m K e y %
627 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
629 % GetRandomKey() gets a random key from the reservoir.
631 % The format of the GetRandomKey method is:
633 % StringInfo *GetRandomKey(RandomInfo *random_info,const size_t length)
635 % A description of each parameter follows:
637 % o random_info: the random info.
639 % o length: the key length.
642 MagickExport StringInfo *GetRandomKey(RandomInfo *random_info,
648 assert(random_info != (RandomInfo *) NULL);
649 key=AcquireStringInfo(length);
650 SetRandomKey(random_info,length,GetStringInfoDatum(key));
655 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
659 % G e t R a n d o m V a l u e %
663 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
665 % GetRandomValue() return a non-negative double-precision floating-point
666 % value uniformly distributed over the interval [0.0, 1.0) with a 2 to the
667 % 128th-1 period (not cryptographically strong).
669 % The format of the GetRandomValue method is:
671 % double GetRandomValue(void)
674 MagickExport double GetRandomValue(RandomInfo *random_info)
683 SetRandomKey(random_info,sizeof(key),(unsigned char *) &key);
684 } while (key == range);
685 return((double) key/range);
689 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
693 + R a n d o m C o m p o n e n t G e n e s i s %
697 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
699 % RandomComponentGenesis() instantiates the random component.
701 % The format of the RandomComponentGenesis method is:
703 % MagickBooleanType RandomComponentGenesis(void)
706 MagickPrivate MagickBooleanType RandomComponentGenesis(void)
708 AcquireSemaphoreInfo(&random_semaphore);
713 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
717 + R a n d o m C o m p o n e n t T e r m i n u s %
721 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
723 % RandomComponentTerminus() destroys the random component.
725 % The format of the RandomComponentTerminus method is:
727 % RandomComponentTerminus(void)
730 MagickPrivate void RandomComponentTerminus(void)
732 if (random_semaphore == (SemaphoreInfo *) NULL)
733 AcquireSemaphoreInfo(&random_semaphore);
734 DestroySemaphoreInfo(&random_semaphore);
738 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
742 % S e e d P s e u d o R a n d o m G e n e r a t o r %
746 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
748 % SeedPseudoRandomGenerator() initializes the pseudo-random number generator
749 % with a random seed.
751 % The format of the SeedPseudoRandomGenerator method is:
753 % void SeedPseudoRandomGenerator(const unsigned long seed)
755 % A description of each parameter follows:
760 MagickExport void SeedPseudoRandomGenerator(const unsigned long seed)
766 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
770 % S e t R a n d o m K e y %
774 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
776 % SetRandomKey() sets a random key from the reservoir.
778 % The format of the SetRandomKey method is:
780 % void SetRandomKey(RandomInfo *random_info,const size_t length,
781 % unsigned char *key)
783 % A description of each parameter follows:
785 % o random_info: the random info.
787 % o length: the key length.
793 static inline void IncrementRandomNonce(StringInfo *nonce)
801 datum=GetStringInfoDatum(nonce);
802 for (i=(ssize_t) (GetStringInfoLength(nonce)-1); i != 0; i--)
808 ThrowFatalException(RandomFatalError,"SequenceWrapError");
811 MagickExport void SetRandomKey(RandomInfo *random_info,const size_t length,
817 register unsigned char
826 assert(random_info != (RandomInfo *) NULL);
829 LockSemaphoreInfo(random_info->semaphore);
830 signature_info=random_info->signature_info;
831 datum=GetStringInfoDatum(random_info->reservoir);
833 for (p=key; (i != 0) && (random_info->i != 0); i--)
835 *p++=datum[random_info->i];
837 if (random_info->i == GetSignatureDigestsize(signature_info))
840 while (i >= GetSignatureDigestsize(signature_info))
842 InitializeSignature(signature_info);
843 UpdateSignature(signature_info,random_info->nonce);
844 FinalizeSignature(signature_info);
845 IncrementRandomNonce(random_info->nonce);
846 (void) CopyMagickMemory(p,GetStringInfoDatum(GetSignatureDigest(
847 signature_info)),GetSignatureDigestsize(signature_info));
848 p+=GetSignatureDigestsize(signature_info);
849 i-=GetSignatureDigestsize(signature_info);
853 InitializeSignature(signature_info);
854 UpdateSignature(signature_info,random_info->nonce);
855 FinalizeSignature(signature_info);
856 IncrementRandomNonce(random_info->nonce);
857 SetStringInfo(random_info->reservoir,GetSignatureDigest(signature_info));
859 datum=GetStringInfoDatum(random_info->reservoir);
863 UnlockSemaphoreInfo(random_info->semaphore);
867 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
871 % S e t R a n d o m T r u e R a n d o m %
875 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
877 % SetRandomTrueRandom() declares your intentions to use true random numbers.
878 % True random numbers are encouraged but may not always be practical because
879 % your application may block while entropy is gathered from your environment.
881 % The format of the SetRandomTrueRandom method is:
883 % void SetRandomTrueRandom(const MagickBooleanType true_random)
885 % A description of each parameter follows:
887 % o true_random: declare your intentions to use true-random number.
890 MagickExport void SetRandomTrueRandom(const MagickBooleanType true_random)
892 gather_true_random=true_random;