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-2012 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"
63 #include "MagickCore/utility-private.h"
67 #define PseudoRandomHash SHA256Hash
68 #define RandomEntropyLevel 9
69 #define RandomFilename "reservoir.xdm"
70 #define RandomFiletype "random"
71 #define RandomProtocolMajorVersion 1
72 #define RandomProtocolMinorVersion 0
110 External declarations.
112 #if defined(__APPLE__) && !defined(TARGET_OS_IPHONE)
113 #include <crt_externs.h>
114 #define environ (*_NSGetEnviron())
124 *random_semaphore = (SemaphoreInfo *) NULL;
129 static MagickBooleanType
130 gather_true_random = MagickFalse;
133 Forward declarations.
136 *GenerateEntropicChaos(RandomInfo *);
139 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
143 % A c q u i r e R a n d o m I n f o %
147 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
149 % AcquireRandomInfo() allocates the RandomInfo structure.
151 % The format of the AcquireRandomInfo method is:
153 % RandomInfo *AcquireRandomInfo(void)
157 static inline size_t MagickMin(const size_t x,const size_t y)
164 MagickExport RandomInfo *AcquireRandomInfo(void)
177 random_info=(RandomInfo *) AcquireMagickMemory(sizeof(*random_info));
178 if (random_info == (RandomInfo *) NULL)
179 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
180 (void) ResetMagickMemory(random_info,0,sizeof(*random_info));
181 random_info->signature_info=AcquireSignatureInfo();
182 random_info->nonce=AcquireStringInfo(2*GetSignatureDigestsize(
183 random_info->signature_info));
184 ResetStringInfo(random_info->nonce);
185 random_info->reservoir=AcquireStringInfo(GetSignatureDigestsize(
186 random_info->signature_info));
187 ResetStringInfo(random_info->reservoir);
188 random_info->normalize=1.0/(~0UL);
189 random_info->semaphore=AllocateSemaphoreInfo();
190 random_info->protocol_major=RandomProtocolMajorVersion;
191 random_info->protocol_minor=RandomProtocolMinorVersion;
192 random_info->timestamp=(ssize_t) time(0);
193 random_info->signature=MagickSignature;
197 nonce=GenerateEntropicChaos(random_info);
198 if (nonce == (StringInfo *) NULL)
199 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
200 InitializeSignature(random_info->signature_info);
201 UpdateSignature(random_info->signature_info,nonce);
202 FinalizeSignature(random_info->signature_info);
203 SetStringInfoLength(nonce,(GetSignatureDigestsize(
204 random_info->signature_info)+1)/2);
205 SetStringInfo(nonce,GetSignatureDigest(random_info->signature_info));
206 SetStringInfo(random_info->nonce,nonce);
207 nonce=DestroyStringInfo(nonce);
209 Seed random reservoir with entropic data.
211 entropy=GenerateEntropicChaos(random_info);
212 if (entropy == (StringInfo *) NULL)
213 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
214 UpdateSignature(random_info->signature_info,entropy);
215 FinalizeSignature(random_info->signature_info);
216 SetStringInfo(random_info->reservoir,GetSignatureDigest(
217 random_info->signature_info));
218 entropy=DestroyStringInfo(entropy);
220 Seed pseudo random number generator.
222 if (random_seed == ~0UL)
224 key=GetRandomKey(random_info,sizeof(random_seed));
225 (void) CopyMagickMemory(random_info->seed,GetStringInfoDatum(key),
226 GetStringInfoLength(key));
227 key=DestroyStringInfo(key);
234 signature_info=AcquireSignatureInfo();
235 key=AcquireStringInfo(sizeof(random_seed));
236 SetStringInfoDatum(key,(unsigned char *) &random_seed);
237 UpdateSignature(signature_info,key);
238 key=DestroyStringInfo(key);
239 FinalizeSignature(signature_info);
240 digest=GetSignatureDigest(signature_info);
241 (void) CopyMagickMemory(random_info->seed,GetStringInfoDatum(digest),
242 MagickMin(GetSignatureDigestsize(signature_info),
243 sizeof(*random_info->seed)));
244 signature_info=DestroySignatureInfo(signature_info);
246 random_info->seed[1]=0x50a7f451UL;
247 random_info->seed[2]=0x5365417eUL;
248 random_info->seed[3]=0xc3a4171aUL;
253 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
257 + D e s t r o y R a n d o m I n f o %
261 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
263 % DestroyRandomInfo() deallocates memory associated with the random
266 % The format of the DestroyRandomInfo method is:
268 % RandomInfo *DestroyRandomInfo(RandomInfo *random_info)
270 % A description of each parameter follows:
272 % o random_info: the random info.
275 MagickExport RandomInfo *DestroyRandomInfo(RandomInfo *random_info)
277 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
278 assert(random_info != (RandomInfo *) NULL);
279 assert(random_info->signature == MagickSignature);
280 LockSemaphoreInfo(random_info->semaphore);
281 if (random_info->reservoir != (StringInfo *) NULL)
282 random_info->reservoir=DestroyStringInfo(random_info->reservoir);
283 if (random_info->nonce != (StringInfo *) NULL)
284 random_info->nonce=DestroyStringInfo(random_info->nonce);
285 if (random_info->signature_info != (SignatureInfo *) NULL)
286 random_info->signature_info=DestroySignatureInfo(
287 random_info->signature_info);
288 (void) ResetMagickMemory(random_info->seed,0,sizeof(*random_info->seed));
289 random_info->signature=(~MagickSignature);
290 UnlockSemaphoreInfo(random_info->semaphore);
291 DestroySemaphoreInfo(&random_info->semaphore);
292 random_info=(RandomInfo *) RelinquishMagickMemory(random_info);
297 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
301 + G e n e r a t e E n t r o p i c C h a o s %
305 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
307 % GenerateEntropicChaos() generate entropic chaos used to initialize the
310 % The format of the GenerateEntropicChaos method is:
312 % StringInfo *GenerateEntropicChaos(RandomInfo *random_info)
314 % A description of each parameter follows:
316 % o random_info: the random info.
320 #if !defined(MAGICKCORE_WINDOWS_SUPPORT)
321 static ssize_t ReadRandom(int file,unsigned char *source,size_t length)
323 register unsigned char
331 for (q=source; length != 0; length-=count)
333 count=(ssize_t) read(file,q,length);
348 static StringInfo *GenerateEntropicChaos(RandomInfo *random_info)
350 #define MaxEntropyExtent 64
367 Initialize random reservoir.
369 entropy=AcquireStringInfo(0);
370 LockSemaphoreInfo(random_info->semaphore);
371 chaos=AcquireStringInfo(sizeof(unsigned char *));
372 SetStringInfoDatum(chaos,(unsigned char *) &entropy);
373 ConcatenateStringInfo(entropy,chaos);
374 SetStringInfoDatum(chaos,(unsigned char *) entropy);
375 ConcatenateStringInfo(entropy,chaos);
376 pid=(ssize_t) getpid();
377 SetStringInfoLength(chaos,sizeof(pid));
378 SetStringInfoDatum(chaos,(unsigned char *) &pid);
379 ConcatenateStringInfo(entropy,chaos);
380 tid=GetMagickThreadId();
381 SetStringInfoLength(chaos,sizeof(tid));
382 SetStringInfoDatum(chaos,(unsigned char *) &tid);
383 ConcatenateStringInfo(entropy,chaos);
384 #if defined(MAGICKCORE_HAVE_GETRUSAGE) && defined(RUSAGE_SELF)
389 if (getrusage(RUSAGE_SELF,&usage) == 0)
391 SetStringInfoLength(chaos,sizeof(usage));
392 SetStringInfoDatum(chaos,(unsigned char *) &usage);
396 seconds=time((time_t *) 0);
398 #if defined(MAGICKCORE_HAVE_GETTIMEOFDAY)
403 if (gettimeofday(&timer,(struct timezone *) NULL) == 0)
405 seconds=timer.tv_sec;
406 nanoseconds=1000UL*timer.tv_usec;
410 #if defined(MAGICKCORE_HAVE_CLOCK_GETTIME) && defined(CLOCK_REALTIME_HR)
415 if (clock_gettime(CLOCK_REALTIME_HR,&timer) == 0)
417 seconds=timer.tv_sec;
418 nanoseconds=timer.tv_nsec;
422 SetStringInfoLength(chaos,sizeof(seconds));
423 SetStringInfoDatum(chaos,(unsigned char *) &seconds);
424 ConcatenateStringInfo(entropy,chaos);
425 SetStringInfoLength(chaos,sizeof(nanoseconds));
426 SetStringInfoDatum(chaos,(unsigned char *) &nanoseconds);
427 ConcatenateStringInfo(entropy,chaos);
429 #if defined(MAGICKCORE_HAVE_CLOCK)
432 #if defined(MAGICKCORE_HAVE_TIMES)
437 (void) times(&timer);
438 nanoseconds=timer.tms_utime+timer.tms_stime;
441 SetStringInfoLength(chaos,sizeof(nanoseconds));
442 SetStringInfoDatum(chaos,(unsigned char *) &nanoseconds);
443 ConcatenateStringInfo(entropy,chaos);
444 #if defined(MAGICKCORE_HAVE_MKSTEMP)
452 filename=ConstantString("magickXXXXXX");
453 file=mkstemp(filename);
455 setmode(file,O_BINARY);
459 (void) remove_utf8(filename);
460 SetStringInfoLength(chaos,strlen(filename));
461 SetStringInfoDatum(chaos,(unsigned char *) filename);
462 ConcatenateStringInfo(entropy,chaos);
463 filename=DestroyString(filename);
466 #if defined(MAGICKCORE_WINDOWS_SUPPORT)
478 Not crytographically strong but better than nothing.
480 seconds=NTElapsedTime()+NTUserTime();
481 SetStringInfoLength(chaos,sizeof(seconds));
482 SetStringInfoDatum(chaos,(unsigned char *) &seconds);
483 ConcatenateStringInfo(entropy,chaos);
484 if (QueryPerformanceCounter(&nanoseconds) != 0)
486 SetStringInfoLength(chaos,sizeof(nanoseconds));
487 SetStringInfoDatum(chaos,(unsigned char *) &nanoseconds);
488 ConcatenateStringInfo(entropy,chaos);
491 Our best hope for true entropy.
493 SetStringInfoLength(chaos,MaxEntropyExtent);
494 status=NTGatherRandomData(MaxEntropyExtent,GetStringInfoDatum(chaos));
496 ConcatenateStringInfo(entropy,chaos);
513 Not crytographically strong but better than nothing.
515 if (environ != (char **) NULL)
521 Squeeze some entropy from the sometimes unpredicatble environment.
523 for (i=0; environ[i] != (char *) NULL; i++)
525 SetStringInfoLength(chaos,strlen(environ[i]));
526 SetStringInfoDatum(chaos,(unsigned char *) environ[i]);
527 ConcatenateStringInfo(entropy,chaos);
530 filename=AcquireString("/dev/urandom");
531 device=StringToStringInfo(filename);
532 device=DestroyStringInfo(device);
533 file=open_utf8(filename,O_RDONLY | O_BINARY,0);
534 filename=DestroyString(filename);
537 SetStringInfoLength(chaos,MaxEntropyExtent);
538 count=ReadRandom(file,GetStringInfoDatum(chaos),MaxEntropyExtent);
540 SetStringInfoLength(chaos,(size_t) count);
541 ConcatenateStringInfo(entropy,chaos);
543 if (gather_true_random != MagickFalse)
546 Our best hope for true entropy.
548 filename=AcquireString("/dev/random");
549 device=StringToStringInfo(filename);
550 device=DestroyStringInfo(device);
551 file=open_utf8(filename,O_RDONLY | O_BINARY,0);
552 filename=DestroyString(filename);
555 filename=AcquireString("/dev/srandom");
556 device=StringToStringInfo(filename);
557 device=DestroyStringInfo(device);
558 file=open_utf8(filename,O_RDONLY | O_BINARY,0);
562 SetStringInfoLength(chaos,MaxEntropyExtent);
563 count=ReadRandom(file,GetStringInfoDatum(chaos),MaxEntropyExtent);
565 SetStringInfoLength(chaos,(size_t) count);
566 ConcatenateStringInfo(entropy,chaos);
571 chaos=DestroyStringInfo(chaos);
572 UnlockSemaphoreInfo(random_info->semaphore);
577 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
581 % G e t P s e u d o R a n d o m V a l u e %
585 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
587 % GetPseudoRandomValue() return a non-negative double-precision floating-point
588 % value uniformly distributed over the interval [0.0, 1.0) with a 2 to the
591 % The format of the GetPseudoRandomValue method is:
593 % double GetPseudoRandomValue(RandomInfo *randon_info)
595 % A description of each parameter follows:
597 % o random_info: the random info.
600 MagickExport double GetPseudoRandomValue(RandomInfo *random_info)
602 register unsigned long
608 seed=random_info->seed;
611 alpha=(unsigned long) (seed[1] ^ (seed[1] << 11));
615 seed[0]=(seed[0] ^ (seed[0] >> 19)) ^ (alpha ^ (alpha >> 8));
616 } while (seed[0] == ~0UL);
617 return(random_info->normalize*seed[0]);
621 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
625 % G e t R a n d o m K e y %
629 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
631 % GetRandomKey() gets a random key from the reservoir.
633 % The format of the GetRandomKey method is:
635 % StringInfo *GetRandomKey(RandomInfo *random_info,const size_t length)
637 % A description of each parameter follows:
639 % o random_info: the random info.
641 % o length: the key length.
644 MagickExport StringInfo *GetRandomKey(RandomInfo *random_info,
650 assert(random_info != (RandomInfo *) NULL);
651 key=AcquireStringInfo(length);
652 SetRandomKey(random_info,length,GetStringInfoDatum(key));
657 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
661 % G e t R a n d o m V a l u e %
665 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
667 % GetRandomValue() return a non-negative double-precision floating-point
668 % value uniformly distributed over the interval [0.0, 1.0) with a 2 to the
669 % 128th-1 period (not cryptographically strong).
671 % The format of the GetRandomValue method is:
673 % double GetRandomValue(void)
676 MagickExport double GetRandomValue(RandomInfo *random_info)
685 SetRandomKey(random_info,sizeof(key),(unsigned char *) &key);
686 } while (key == range);
687 return((double) key/range);
691 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
695 + R a n d o m C o m p o n e n t G e n e s i s %
699 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
701 % RandomComponentGenesis() instantiates the random component.
703 % The format of the RandomComponentGenesis method is:
705 % MagickBooleanType RandomComponentGenesis(void)
708 MagickPrivate MagickBooleanType RandomComponentGenesis(void)
710 AcquireSemaphoreInfo(&random_semaphore);
715 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
719 + R a n d o m C o m p o n e n t T e r m i n u s %
723 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
725 % RandomComponentTerminus() destroys the random component.
727 % The format of the RandomComponentTerminus method is:
729 % RandomComponentTerminus(void)
732 MagickPrivate void RandomComponentTerminus(void)
734 if (random_semaphore == (SemaphoreInfo *) NULL)
735 AcquireSemaphoreInfo(&random_semaphore);
736 DestroySemaphoreInfo(&random_semaphore);
740 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
744 % 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 %
748 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
750 % SeedPseudoRandomGenerator() initializes the pseudo-random number generator
751 % with a random seed.
753 % The format of the SeedPseudoRandomGenerator method is:
755 % void SeedPseudoRandomGenerator(const unsigned long seed)
757 % A description of each parameter follows:
762 MagickExport void SeedPseudoRandomGenerator(const unsigned long seed)
768 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
772 % S e t R a n d o m K e y %
776 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
778 % SetRandomKey() sets a random key from the reservoir.
780 % The format of the SetRandomKey method is:
782 % void SetRandomKey(RandomInfo *random_info,const size_t length,
783 % unsigned char *key)
785 % A description of each parameter follows:
787 % o random_info: the random info.
789 % o length: the key length.
795 static inline void IncrementRandomNonce(StringInfo *nonce)
803 datum=GetStringInfoDatum(nonce);
804 for (i=(ssize_t) (GetStringInfoLength(nonce)-1); i != 0; i--)
810 ThrowFatalException(RandomFatalError,"SequenceWrapError");
813 MagickExport void SetRandomKey(RandomInfo *random_info,const size_t length,
819 register unsigned char
828 assert(random_info != (RandomInfo *) NULL);
831 LockSemaphoreInfo(random_info->semaphore);
832 signature_info=random_info->signature_info;
833 datum=GetStringInfoDatum(random_info->reservoir);
835 for (p=key; (i != 0) && (random_info->i != 0); i--)
837 *p++=datum[random_info->i];
839 if (random_info->i == GetSignatureDigestsize(signature_info))
842 while (i >= GetSignatureDigestsize(signature_info))
844 InitializeSignature(signature_info);
845 UpdateSignature(signature_info,random_info->nonce);
846 FinalizeSignature(signature_info);
847 IncrementRandomNonce(random_info->nonce);
848 (void) CopyMagickMemory(p,GetStringInfoDatum(GetSignatureDigest(
849 signature_info)),GetSignatureDigestsize(signature_info));
850 p+=GetSignatureDigestsize(signature_info);
851 i-=GetSignatureDigestsize(signature_info);
855 InitializeSignature(signature_info);
856 UpdateSignature(signature_info,random_info->nonce);
857 FinalizeSignature(signature_info);
858 IncrementRandomNonce(random_info->nonce);
859 SetStringInfo(random_info->reservoir,GetSignatureDigest(signature_info));
861 datum=GetStringInfoDatum(random_info->reservoir);
865 UnlockSemaphoreInfo(random_info->semaphore);
869 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
873 % S e t R a n d o m T r u e R a n d o m %
877 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
879 % SetRandomTrueRandom() declares your intentions to use true random numbers.
880 % True random numbers are encouraged but may not always be practical because
881 % your application may block while entropy is gathered from your environment.
883 % The format of the SetRandomTrueRandom method is:
885 % void SetRandomTrueRandom(const MagickBooleanType true_random)
887 % A description of each parameter follows:
889 % o true_random: declare your intentions to use true-random number.
892 MagickExport void SetRandomTrueRandom(const MagickBooleanType true_random)
894 gather_true_random=true_random;