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));
495 ConcatenateStringInfo(entropy,chaos);
512 Not crytographically strong but better than nothing.
514 if (environ != (char **) NULL)
520 Squeeze some entropy from the sometimes unpredicatble environment.
522 for (i=0; environ[i] != (char *) NULL; i++)
524 SetStringInfoLength(chaos,strlen(environ[i]));
525 SetStringInfoDatum(chaos,(unsigned char *) environ[i]);
526 ConcatenateStringInfo(entropy,chaos);
529 filename=AcquireString("/dev/urandom");
530 device=StringToStringInfo(filename);
531 device=DestroyStringInfo(device);
532 file=open_utf8(filename,O_RDONLY | O_BINARY,0);
533 filename=DestroyString(filename);
536 SetStringInfoLength(chaos,MaxEntropyExtent);
537 count=ReadRandom(file,GetStringInfoDatum(chaos),MaxEntropyExtent);
539 SetStringInfoLength(chaos,(size_t) count);
540 ConcatenateStringInfo(entropy,chaos);
542 if (gather_true_random != MagickFalse)
545 Our best hope for true entropy.
547 filename=AcquireString("/dev/random");
548 device=StringToStringInfo(filename);
549 device=DestroyStringInfo(device);
550 file=open_utf8(filename,O_RDONLY | O_BINARY,0);
551 filename=DestroyString(filename);
554 filename=AcquireString("/dev/srandom");
555 device=StringToStringInfo(filename);
556 device=DestroyStringInfo(device);
557 file=open_utf8(filename,O_RDONLY | O_BINARY,0);
561 SetStringInfoLength(chaos,MaxEntropyExtent);
562 count=ReadRandom(file,GetStringInfoDatum(chaos),MaxEntropyExtent);
564 SetStringInfoLength(chaos,(size_t) count);
565 ConcatenateStringInfo(entropy,chaos);
570 chaos=DestroyStringInfo(chaos);
571 UnlockSemaphoreInfo(random_info->semaphore);
576 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
580 % G e t P s e u d o R a n d o m V a l u e %
584 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
586 % GetPseudoRandomValue() return a non-negative double-precision floating-point
587 % value uniformly distributed over the interval [0.0, 1.0) with a 2 to the
590 % The format of the GetPseudoRandomValue method is:
592 % double GetPseudoRandomValue(RandomInfo *randon_info)
594 % A description of each parameter follows:
596 % o random_info: the random info.
599 MagickExport double GetPseudoRandomValue(RandomInfo *random_info)
601 register unsigned long
607 seed=random_info->seed;
610 alpha=(unsigned long) (seed[1] ^ (seed[1] << 11));
614 seed[0]=(seed[0] ^ (seed[0] >> 19)) ^ (alpha ^ (alpha >> 8));
615 } while (seed[0] == ~0UL);
616 return(random_info->normalize*seed[0]);
620 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
624 % G e t R a n d o m K e y %
628 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
630 % GetRandomKey() gets a random key from the reservoir.
632 % The format of the GetRandomKey method is:
634 % StringInfo *GetRandomKey(RandomInfo *random_info,const size_t length)
636 % A description of each parameter follows:
638 % o random_info: the random info.
640 % o length: the key length.
643 MagickExport StringInfo *GetRandomKey(RandomInfo *random_info,
649 assert(random_info != (RandomInfo *) NULL);
650 key=AcquireStringInfo(length);
651 SetRandomKey(random_info,length,GetStringInfoDatum(key));
656 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
660 % G e t R a n d o m V a l u e %
664 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
666 % GetRandomValue() return a non-negative double-precision floating-point
667 % value uniformly distributed over the interval [0.0, 1.0) with a 2 to the
668 % 128th-1 period (not cryptographically strong).
670 % The format of the GetRandomValue method is:
672 % double GetRandomValue(void)
675 MagickExport double GetRandomValue(RandomInfo *random_info)
684 SetRandomKey(random_info,sizeof(key),(unsigned char *) &key);
685 } while (key == range);
686 return((double) key/range);
690 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
694 + R a n d o m C o m p o n e n t G e n e s i s %
698 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
700 % RandomComponentGenesis() instantiates the random component.
702 % The format of the RandomComponentGenesis method is:
704 % MagickBooleanType RandomComponentGenesis(void)
707 MagickPrivate MagickBooleanType RandomComponentGenesis(void)
709 AcquireSemaphoreInfo(&random_semaphore);
714 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
718 + R a n d o m C o m p o n e n t T e r m i n u s %
722 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
724 % RandomComponentTerminus() destroys the random component.
726 % The format of the RandomComponentTerminus method is:
728 % RandomComponentTerminus(void)
731 MagickPrivate void RandomComponentTerminus(void)
733 if (random_semaphore == (SemaphoreInfo *) NULL)
734 AcquireSemaphoreInfo(&random_semaphore);
735 DestroySemaphoreInfo(&random_semaphore);
739 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
743 % 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 %
747 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
749 % SeedPseudoRandomGenerator() initializes the pseudo-random number generator
750 % with a random seed.
752 % The format of the SeedPseudoRandomGenerator method is:
754 % void SeedPseudoRandomGenerator(const unsigned long seed)
756 % A description of each parameter follows:
761 MagickExport void SeedPseudoRandomGenerator(const unsigned long seed)
767 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
771 % S e t R a n d o m K e y %
775 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
777 % SetRandomKey() sets a random key from the reservoir.
779 % The format of the SetRandomKey method is:
781 % void SetRandomKey(RandomInfo *random_info,const size_t length,
782 % unsigned char *key)
784 % A description of each parameter follows:
786 % o random_info: the random info.
788 % o length: the key length.
794 static inline void IncrementRandomNonce(StringInfo *nonce)
802 datum=GetStringInfoDatum(nonce);
803 for (i=(ssize_t) (GetStringInfoLength(nonce)-1); i != 0; i--)
809 ThrowFatalException(RandomFatalError,"SequenceWrapError");
812 MagickExport void SetRandomKey(RandomInfo *random_info,const size_t length,
818 register unsigned char
827 assert(random_info != (RandomInfo *) NULL);
830 LockSemaphoreInfo(random_info->semaphore);
831 signature_info=random_info->signature_info;
832 datum=GetStringInfoDatum(random_info->reservoir);
834 for (p=key; (i != 0) && (random_info->i != 0); i--)
836 *p++=datum[random_info->i];
838 if (random_info->i == GetSignatureDigestsize(signature_info))
841 while (i >= GetSignatureDigestsize(signature_info))
843 InitializeSignature(signature_info);
844 UpdateSignature(signature_info,random_info->nonce);
845 FinalizeSignature(signature_info);
846 IncrementRandomNonce(random_info->nonce);
847 (void) CopyMagickMemory(p,GetStringInfoDatum(GetSignatureDigest(
848 signature_info)),GetSignatureDigestsize(signature_info));
849 p+=GetSignatureDigestsize(signature_info);
850 i-=GetSignatureDigestsize(signature_info);
854 InitializeSignature(signature_info);
855 UpdateSignature(signature_info,random_info->nonce);
856 FinalizeSignature(signature_info);
857 IncrementRandomNonce(random_info->nonce);
858 SetStringInfo(random_info->reservoir,GetSignatureDigest(signature_info));
860 datum=GetStringInfoDatum(random_info->reservoir);
864 UnlockSemaphoreInfo(random_info->semaphore);
868 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
872 % S e t R a n d o m T r u e R a n d o m %
876 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
878 % SetRandomTrueRandom() declares your intentions to use true random numbers.
879 % True random numbers are encouraged but may not always be practical because
880 % your application may block while entropy is gathered from your environment.
882 % The format of the SetRandomTrueRandom method is:
884 % void SetRandomTrueRandom(const MagickBooleanType true_random)
886 % A description of each parameter follows:
888 % o true_random: declare your intentions to use true-random number.
891 MagickExport void SetRandomTrueRandom(const MagickBooleanType true_random)
893 gather_true_random=true_random;