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 "magick/studio.h"
51 #include "magick/exception.h"
52 #include "magick/exception-private.h"
53 #include "magick/memory_.h"
54 #include "magick/semaphore.h"
55 #include "magick/random_.h"
56 #include "magick/resource_.h"
57 #include "magick/signature-private.h"
58 #include "magick/string_.h"
59 #include "magick/thread_.h"
60 #include "magick/thread-private.h"
61 #include "magick/utility.h"
65 #define PseudoRandomHash SHA256Hash
66 #define RandomEntropyLevel 9
67 #define RandomFilename "reservoir.xdm"
68 #define RandomFiletype "random"
69 #define RandomProtocolMajorVersion 1
70 #define RandomProtocolMinorVersion 0
108 External declarations.
110 #if defined(__APPLE__) && !defined(TARGET_OS_IPHONE)
111 #include <crt_externs.h>
112 #define environ (*_NSGetEnviron())
122 *random_semaphore = (SemaphoreInfo *) NULL;
127 static MagickBooleanType
128 gather_true_random = MagickFalse;
131 Forward declarations.
134 *GenerateEntropicChaos(RandomInfo *);
137 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
141 % A c q u i r e R a n d o m I n f o %
145 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
147 % AcquireRandomInfo() allocates the RandomInfo structure.
149 % The format of the AcquireRandomInfo method is:
151 % RandomInfo *AcquireRandomInfo(void)
155 static inline size_t MagickMin(const size_t x,const size_t y)
162 MagickExport RandomInfo *AcquireRandomInfo(void)
175 random_info=(RandomInfo *) AcquireMagickMemory(sizeof(*random_info));
176 if (random_info == (RandomInfo *) NULL)
177 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
178 (void) ResetMagickMemory(random_info,0,sizeof(*random_info));
179 random_info->signature_info=AcquireSignatureInfo();
180 random_info->nonce=AcquireStringInfo(2*GetSignatureDigestsize(
181 random_info->signature_info));
182 ResetStringInfo(random_info->nonce);
183 random_info->reservoir=AcquireStringInfo(GetSignatureDigestsize(
184 random_info->signature_info));
185 ResetStringInfo(random_info->reservoir);
186 random_info->normalize=1.0/(~0UL);
187 random_info->semaphore=AllocateSemaphoreInfo();
188 random_info->protocol_major=RandomProtocolMajorVersion;
189 random_info->protocol_minor=RandomProtocolMinorVersion;
190 random_info->timestamp=(ssize_t) time(0);
191 random_info->signature=MagickSignature;
195 nonce=GenerateEntropicChaos(random_info);
196 if (nonce == (StringInfo *) NULL)
197 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
198 InitializeSignature(random_info->signature_info);
199 UpdateSignature(random_info->signature_info,nonce);
200 FinalizeSignature(random_info->signature_info);
201 SetStringInfoLength(nonce,(GetSignatureDigestsize(
202 random_info->signature_info)+1)/2);
203 SetStringInfo(nonce,GetSignatureDigest(random_info->signature_info));
204 SetStringInfo(random_info->nonce,nonce);
205 nonce=DestroyStringInfo(nonce);
207 Seed random reservoir with entropic data.
209 entropy=GenerateEntropicChaos(random_info);
210 if (entropy == (StringInfo *) NULL)
211 ThrowFatalException(ResourceLimitFatalError,"MemoryAllocationFailed");
212 UpdateSignature(random_info->signature_info,entropy);
213 FinalizeSignature(random_info->signature_info);
214 SetStringInfo(random_info->reservoir,GetSignatureDigest(
215 random_info->signature_info));
216 entropy=DestroyStringInfo(entropy);
218 Seed pseudo random number generator.
220 if (random_seed == ~0UL)
222 key=GetRandomKey(random_info,sizeof(random_seed));
223 (void) CopyMagickMemory(random_info->seed,GetStringInfoDatum(key),
224 GetStringInfoLength(key));
225 key=DestroyStringInfo(key);
232 signature_info=AcquireSignatureInfo();
233 key=AcquireStringInfo(sizeof(random_seed));
234 SetStringInfoDatum(key,(unsigned char *) &random_seed);
235 UpdateSignature(signature_info,key);
236 key=DestroyStringInfo(key);
237 FinalizeSignature(signature_info);
238 digest=GetSignatureDigest(signature_info);
239 (void) CopyMagickMemory(random_info->seed,GetStringInfoDatum(digest),
240 MagickMin(GetSignatureDigestsize(signature_info),
241 sizeof(*random_info->seed)));
242 signature_info=DestroySignatureInfo(signature_info);
244 random_info->seed[1]=0x50a7f451UL;
245 random_info->seed[2]=0x5365417eUL;
246 random_info->seed[3]=0xc3a4171aUL;
251 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
255 + D e s t r o y R a n d o m I n f o %
259 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
261 % DestroyRandomInfo() deallocates memory associated with the random
264 % The format of the DestroyRandomInfo method is:
266 % RandomInfo *DestroyRandomInfo(RandomInfo *random_info)
268 % A description of each parameter follows:
270 % o random_info: the random info.
273 MagickExport RandomInfo *DestroyRandomInfo(RandomInfo *random_info)
275 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"...");
276 assert(random_info != (RandomInfo *) NULL);
277 assert(random_info->signature == MagickSignature);
278 LockSemaphoreInfo(random_info->semaphore);
279 if (random_info->reservoir != (StringInfo *) NULL)
280 random_info->reservoir=DestroyStringInfo(random_info->reservoir);
281 if (random_info->nonce != (StringInfo *) NULL)
282 random_info->nonce=DestroyStringInfo(random_info->nonce);
283 if (random_info->signature_info != (SignatureInfo *) NULL)
284 random_info->signature_info=DestroySignatureInfo(
285 random_info->signature_info);
286 (void) ResetMagickMemory(random_info->seed,0,sizeof(*random_info->seed));
287 random_info->signature=(~MagickSignature);
288 UnlockSemaphoreInfo(random_info->semaphore);
289 DestroySemaphoreInfo(&random_info->semaphore);
290 random_info=(RandomInfo *) RelinquishMagickMemory(random_info);
295 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
299 + G e n e r a t e E n t r o p i c C h a o s %
303 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
305 % GenerateEntropicChaos() generate entropic chaos used to initialize the
308 % The format of the GenerateEntropicChaos method is:
310 % StringInfo *GenerateEntropicChaos(RandomInfo *random_info)
312 % A description of each parameter follows:
314 % o random_info: the random info.
318 #if !defined(MAGICKCORE_WINDOWS_SUPPORT)
319 static ssize_t ReadRandom(int file,unsigned char *source,size_t length)
321 register unsigned char
329 for (q=source; length != 0; length-=count)
331 count=(ssize_t) read(file,q,length);
346 static StringInfo *GenerateEntropicChaos(RandomInfo *random_info)
348 #define MaxEntropyExtent 64
365 Initialize random reservoir.
367 entropy=AcquireStringInfo(0);
368 LockSemaphoreInfo(random_info->semaphore);
369 chaos=AcquireStringInfo(sizeof(unsigned char *));
370 SetStringInfoDatum(chaos,(unsigned char *) &entropy);
371 ConcatenateStringInfo(entropy,chaos);
372 SetStringInfoDatum(chaos,(unsigned char *) entropy);
373 ConcatenateStringInfo(entropy,chaos);
374 pid=(ssize_t) getpid();
375 SetStringInfoLength(chaos,sizeof(pid));
376 SetStringInfoDatum(chaos,(unsigned char *) &pid);
377 ConcatenateStringInfo(entropy,chaos);
378 tid=GetMagickThreadId();
379 SetStringInfoLength(chaos,sizeof(tid));
380 SetStringInfoDatum(chaos,(unsigned char *) &tid);
381 ConcatenateStringInfo(entropy,chaos);
382 #if defined(MAGICKCORE_HAVE_GETRUSAGE) && defined(RUSAGE_SELF)
387 if (getrusage(RUSAGE_SELF,&usage) == 0)
389 SetStringInfoLength(chaos,sizeof(usage));
390 SetStringInfoDatum(chaos,(unsigned char *) &usage);
394 seconds=time((time_t *) 0);
396 #if defined(MAGICKCORE_HAVE_GETTIMEOFDAY)
401 if (gettimeofday(&timer,(struct timezone *) NULL) == 0)
403 seconds=timer.tv_sec;
404 nanoseconds=1000UL*timer.tv_usec;
408 #if defined(MAGICKCORE_HAVE_CLOCK_GETTIME) && defined(CLOCK_REALTIME_HR)
413 if (clock_gettime(CLOCK_REALTIME_HR,&timer) == 0)
415 seconds=timer.tv_sec;
416 nanoseconds=timer.tv_nsec;
420 SetStringInfoLength(chaos,sizeof(seconds));
421 SetStringInfoDatum(chaos,(unsigned char *) &seconds);
422 ConcatenateStringInfo(entropy,chaos);
423 SetStringInfoLength(chaos,sizeof(nanoseconds));
424 SetStringInfoDatum(chaos,(unsigned char *) &nanoseconds);
425 ConcatenateStringInfo(entropy,chaos);
427 #if defined(MAGICKCORE_HAVE_CLOCK)
430 #if defined(MAGICKCORE_HAVE_TIMES)
435 (void) times(&timer);
436 nanoseconds=timer.tms_utime+timer.tms_stime;
439 SetStringInfoLength(chaos,sizeof(nanoseconds));
440 SetStringInfoDatum(chaos,(unsigned char *) &nanoseconds);
441 ConcatenateStringInfo(entropy,chaos);
442 #if defined(MAGICKCORE_HAVE_MKSTEMP)
450 filename=ConstantString("magickXXXXXX");
451 file=mkstemp(filename);
453 setmode(file,O_BINARY);
457 (void) remove(filename);
458 SetStringInfoLength(chaos,strlen(filename));
459 SetStringInfoDatum(chaos,(unsigned char *) filename);
460 ConcatenateStringInfo(entropy,chaos);
461 filename=DestroyString(filename);
464 #if defined(MAGICKCORE_WINDOWS_SUPPORT)
476 Not crytographically strong but better than nothing.
478 seconds=NTElapsedTime()+NTUserTime();
479 SetStringInfoLength(chaos,sizeof(seconds));
480 SetStringInfoDatum(chaos,(unsigned char *) &seconds);
481 ConcatenateStringInfo(entropy,chaos);
482 if (QueryPerformanceCounter(&nanoseconds) != 0)
484 SetStringInfoLength(chaos,sizeof(nanoseconds));
485 SetStringInfoDatum(chaos,(unsigned char *) &nanoseconds);
486 ConcatenateStringInfo(entropy,chaos);
489 Our best hope for true entropy.
491 SetStringInfoLength(chaos,MaxEntropyExtent);
492 status=NTGatherRandomData(MaxEntropyExtent,GetStringInfoDatum(chaos));
493 ConcatenateStringInfo(entropy,chaos);
510 Not crytographically strong but better than nothing.
512 if (environ != (char **) NULL)
518 Squeeze some entropy from the sometimes unpredicatble environment.
520 for (i=0; environ[i] != (char *) NULL; i++)
522 SetStringInfoLength(chaos,strlen(environ[i]));
523 SetStringInfoDatum(chaos,(unsigned char *) environ[i]);
524 ConcatenateStringInfo(entropy,chaos);
527 filename=AcquireString("/dev/urandom");
528 device=StringToStringInfo(filename);
529 device=DestroyStringInfo(device);
530 file=open(filename,O_RDONLY | O_BINARY);
531 filename=DestroyString(filename);
534 SetStringInfoLength(chaos,MaxEntropyExtent);
535 count=ReadRandom(file,GetStringInfoDatum(chaos),MaxEntropyExtent);
537 SetStringInfoLength(chaos,(size_t) count);
538 ConcatenateStringInfo(entropy,chaos);
540 if (gather_true_random != MagickFalse)
543 Our best hope for true entropy.
545 filename=AcquireString("/dev/random");
546 device=StringToStringInfo(filename);
547 device=DestroyStringInfo(device);
548 file=open(filename,O_RDONLY | O_BINARY);
549 filename=DestroyString(filename);
552 filename=AcquireString("/dev/srandom");
553 device=StringToStringInfo(filename);
554 device=DestroyStringInfo(device);
555 file=open(filename,O_RDONLY | O_BINARY);
559 SetStringInfoLength(chaos,MaxEntropyExtent);
560 count=ReadRandom(file,GetStringInfoDatum(chaos),MaxEntropyExtent);
562 SetStringInfoLength(chaos,(size_t) count);
563 ConcatenateStringInfo(entropy,chaos);
568 chaos=DestroyStringInfo(chaos);
569 UnlockSemaphoreInfo(random_info->semaphore);
574 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
578 % G e t P s e u d o R a n d o m V a l u e %
582 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
584 % GetPseudoRandomValue() return a non-negative double-precision floating-point
585 % value uniformly distributed over the interval [0.0, 1.0) with a 2 to the
588 % The format of the GetPseudoRandomValue method is:
590 % double GetPseudoRandomValue(RandomInfo *randon_info)
592 % A description of each parameter follows:
594 % o random_info: the random info.
597 MagickExport double GetPseudoRandomValue(RandomInfo *random_info)
599 register unsigned long
605 seed=random_info->seed;
608 alpha=(unsigned long) (seed[1] ^ (seed[1] << 11));
612 seed[0]=(seed[0] ^ (seed[0] >> 19)) ^ (alpha ^ (alpha >> 8));
613 } while (seed[0] == ~0UL);
614 return(random_info->normalize*seed[0]);
618 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
622 % G e t R a n d o m K e y %
626 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
628 % GetRandomKey() gets a random key from the reservoir.
630 % The format of the GetRandomKey method is:
632 % StringInfo *GetRandomKey(RandomInfo *random_info,const size_t length)
634 % A description of each parameter follows:
636 % o random_info: the random info.
638 % o length: the key length.
641 MagickExport StringInfo *GetRandomKey(RandomInfo *random_info,
647 assert(random_info != (RandomInfo *) NULL);
648 key=AcquireStringInfo(length);
649 SetRandomKey(random_info,length,GetStringInfoDatum(key));
654 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
658 % G e t R a n d o m V a l u e %
662 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
664 % GetRandomValue() return a non-negative double-precision floating-point
665 % value uniformly distributed over the interval [0.0, 1.0) with a 2 to the
666 % 128th-1 period (not cryptographically strong).
668 % The format of the GetRandomValue method is:
670 % double GetRandomValue(void)
673 MagickExport double GetRandomValue(RandomInfo *random_info)
682 SetRandomKey(random_info,sizeof(key),(unsigned char *) &key);
683 } while (key == range);
684 return((double) key/range);
688 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
692 + R a n d o m C o m p o n e n t G e n e s i s %
696 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
698 % RandomComponentGenesis() instantiates the random component.
700 % The format of the RandomComponentGenesis method is:
702 % MagickBooleanType RandomComponentGenesis(void)
705 MagickExport MagickBooleanType RandomComponentGenesis(void)
707 AcquireSemaphoreInfo(&random_semaphore);
712 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
716 + R a n d o m C o m p o n e n t T e r m i n u s %
720 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
722 % RandomComponentTerminus() destroys the random component.
724 % The format of the RandomComponentTerminus method is:
726 % RandomComponentTerminus(void)
729 MagickExport void RandomComponentTerminus(void)
731 if (random_semaphore == (SemaphoreInfo *) NULL)
732 AcquireSemaphoreInfo(&random_semaphore);
733 DestroySemaphoreInfo(&random_semaphore);
737 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
741 % 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 %
745 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
747 % SeedPseudoRandomGenerator() initializes the pseudo-random number generator
748 % with a random seed.
750 % The format of the SeedPseudoRandomGenerator method is:
752 % void SeedPseudoRandomGenerator(const unsigned long seed)
754 % A description of each parameter follows:
759 MagickExport void SeedPseudoRandomGenerator(const unsigned long seed)
765 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
769 % S e t R a n d o m K e y %
773 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
775 % SetRandomKey() sets a random key from the reservoir.
777 % The format of the SetRandomKey method is:
779 % void SetRandomKey(RandomInfo *random_info,const size_t length,
780 % unsigned char *key)
782 % A description of each parameter follows:
784 % o random_info: the random info.
786 % o length: the key length.
792 static inline void IncrementRandomNonce(StringInfo *nonce)
800 datum=GetStringInfoDatum(nonce);
801 for (i=(ssize_t) (GetStringInfoLength(nonce)-1); i != 0; i--)
807 ThrowFatalException(RandomFatalError,"SequenceWrapError");
810 MagickExport void SetRandomKey(RandomInfo *random_info,const size_t length,
816 register unsigned char
825 assert(random_info != (RandomInfo *) NULL);
828 LockSemaphoreInfo(random_info->semaphore);
829 signature_info=random_info->signature_info;
830 datum=GetStringInfoDatum(random_info->reservoir);
832 for (p=key; (i != 0) && (random_info->i != 0); i--)
834 *p++=datum[random_info->i];
836 if (random_info->i == GetSignatureDigestsize(signature_info))
839 while (i >= GetSignatureDigestsize(signature_info))
841 InitializeSignature(signature_info);
842 UpdateSignature(signature_info,random_info->nonce);
843 FinalizeSignature(signature_info);
844 IncrementRandomNonce(random_info->nonce);
845 (void) CopyMagickMemory(p,GetStringInfoDatum(GetSignatureDigest(
846 signature_info)),GetSignatureDigestsize(signature_info));
847 p+=GetSignatureDigestsize(signature_info);
848 i-=GetSignatureDigestsize(signature_info);
852 InitializeSignature(signature_info);
853 UpdateSignature(signature_info,random_info->nonce);
854 FinalizeSignature(signature_info);
855 IncrementRandomNonce(random_info->nonce);
856 SetStringInfo(random_info->reservoir,GetSignatureDigest(signature_info));
858 datum=GetStringInfoDatum(random_info->reservoir);
862 UnlockSemaphoreInfo(random_info->semaphore);
866 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
870 % S e t R a n d o m T r u e R a n d o m %
874 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
876 % SetRandomTrueRandom() declares your intentions to use true random numbers.
877 % True random numbers are encouraged but may not always be practical because
878 % your application may block while entropy is gathered from your environment.
880 % The format of the SetRandomTrueRandom method is:
882 % void SetRandomTrueRandom(const MagickBooleanType true_random)
884 % A description of each parameter follows:
886 % o true_random: declare your intentions to use true-random number.
889 MagickExport void SetRandomTrueRandom(const MagickBooleanType true_random)
891 gather_true_random=true_random;