Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Despite the fact that Marsaglia's MWC PRNG (multiply-with-carry random number generator) is considered to be "the mother of all RNGs", it does not seem to be considered to be a CSPRNG (cryptographically secure pseudo-random number generator) even though it passes several statistical randomness tests, including ENT and Die-Hard.

Considering it's possible to define a seed etc., what is the MWC RNG missing that a CSPRNG has? Simpler asked: "What stops the MWC PRNG from being a CSPRNG?"

CSPRNGs have to pass statistical randomness tests, which MWC RNG seems to satisfy. Also, MWC PRNG allows you to choose random initial as long as c < 809430660, which seems big enough to make it hard for people to analyse which of the 809430659 options you chose to seed the MWC PRNG. And last but not least people call it the "mother of all RNGs" — see "George Marsaglia's "Mother of all RNGs" (C code with comments)" at http://www.stat.berkeley.edu/classes/s243/mother.c — which implies it's about the best (P)RNG out there.

Comparing MWC PRNG with cryptographically secure PRNGs, it shows both are pseudo-random, both produce comparable randomness, and both pass the same statistical tests. Some even claim it has cryptographic quality. Yet, I can not find a single indication that it is cryptographically secure.

Therefore I am wondering and asking: "What stops the MWC PRNG from being a CSPRNG?"

Or, asking in other words:

  • What is the MWC PRNG missing a CSPRNG should have to be cryptographically secure, and/or
  • What does the MWC PRNG have that a CSPRNG should not have to be cryptographically secure?

Currently, I am suspecting I am missing some security definition related to cryptographically secure pseudo-random number generators, or maybe I'm not seeing the obvious security issue which makes the MWC PRNG cryptographically insecure. Therefore, every explanation which could help me understand why the MWC PRNG fails to be classified as a cryptographically secure PRNG is highly appreciated.


In case someone needs some references related to MWC PRNG…

General Wikipedia Description of MWC
http://en.wikipedia.org/wiki/Multiply-with-carry

"George Marsaglia's “Mother of all RNGs” (C code with comments)"
http://www.stat.berkeley.edu/classes/s243/mother.c

And here's a copy of Marsaglia's original publication, which was first published at sci.stat.math…

good C random number generator
From: George Marsaglia (geo@stat.fsu.edu)
Subject: Re: good C random number generator
Newsgroups: comp.lang.c
Date: 2003-05-13 08:55:05 PST
Organization: Florida State University
Lines: 89

Most RNGs work by keeping a certain number, say k, of the most recently generated integers, then return the next integer as a function of those k. The initial k integers, the seeds, are assumed to be randomly chosen, usually 32-bits. The period of the RNG is related to the number of choices for seeds, usually 2^(32k), so to get longer periods you need to increase k.

Probably the most common type has k=1, and needs a single seed, with each new integer a function of the previous one. An example is this congruential RNG, a form of which was the system RNG in VAXs for many years:

   /* a random initial x to be assigned by the calling program */
   static unsigned long x=123456789; 
   unsigned long cong(void )
   { 
       return (x=69069*x+362437);
   }

Simple, k=1, RNGs can perform fairly well in tests of randomness such as those in the new version of Diehard,

   csis.hku.hk/~diehard

but experience has shown that better performances come from RNGs with k's ranging from 4 or 5 to as much as 4097.

Here is an example with k=5, period about 2^160, one of the fastest long period RNGs, returns more than 120 million random 32-bit integers/second (1.8MHz CPU), seems to pass all tests:

   /* replace defaults with five random seed values in calling program */
   static unsigned long x=123456789,y=362436069,z=521288629,w=88675123,v=886756453;
   unsigned long xorshift(void)
   {
       unsigned long t;
       t=(x^(x>>7)); 
       x=y; 
       y=z; 
       z=w; 
       w=v;
       v=(v^(v<<6))^(t^(t<<13)); 
       return (y+y+1)*v;
   }

Another example has k=257, period about 2^8222. Uses a static array Q[256] and an initial carry 'c', the Q array filled with 256 random 32-bit integers in the calling program and an initial carry c<809430660 for the multiply-with-carry operation. It is very fast and seems to pass all tests.

   /* choose random initial c<809430660 and 256 random 32-bit integers for Q[] */
   static unsigned long Q[256],c=362436;  
   unsigned long MWC256(void)
   {
       unsigned long long t,a=809430660LL;
       static unsigned char i=255;
       t=a*Q[++i]+c;
       c=(t>>32);
       return(Q[i]=t);      
   }

The Mersenne Twister (check Google) is an excellent RNG, with k=624. But it requires an elaborate C program and is slower than many RNGs that do as well in tests, have comparable or longer periods and require only a few lines of code.

Here is a complimentary-multiply-with-carry RNG with k=4097 and a near-record period, more than 10^33000 times as long as that of the Twister. (2^131104 vs. 2^19937)

   /* choose random initial c<809430660 and 4096 random 32-bit integers for Q[] */
   static unsigned long Q[4096],c=362436;
   unsigned long CMWC4096(void)
   {
       unsigned long long t, a=18782LL;
       static unsigned long i=4095;
       unsigned long x,r=0xfffffffe;
       i=(i+1)&4095;
       t=a*Q[i]+c;
       c=(t>>32);
       x=t+c; 
       if(x<c)
       {
          x++;
          c++;
       }
       return(Q[i]=r-x);    
   }

You will find several more CMWC RNGs and comments on choice of seeds in the May 2003 Communications of the ACM.

George Marsaglia

share|improve this question
3  
This article may be helpful: eprint.iacr.org/2011/007 The short story is that given MWC output, it's fairly easy to recover internal state and do all kinds of bad things from there. –  Samuel Neves Sep 15 '13 at 18:29
    
@SamuelNeves Thank you - that link is perfect. As it turns out, I've been mislead by reading too many online resources that "claimed that it is of cryptographic quality". Nice find. [+1] –  e-sushi Sep 15 '13 at 18:46
1  
No idea why people care about period length above say $2^{256}$. –  CodesInChaos Sep 15 '13 at 19:22
    
@CodesInChaos Well, "statistical purposes" is the answer I read the most. –  e-sushi Sep 15 '13 at 22:47
    
@e-sushi, "statistical purposes" is not an answer to CodesInChaos's question. There is no statistical simulation ever done that will use $2^{256}$ outputs from such a generator. –  D.W. Sep 24 '13 at 18:47

1 Answer 1

up vote 6 down vote accepted

It fails to be a cryptographically-strong PRNG because it is predictable: given some outputs, you can predict the next outputs. For instance, if you observe the outputs at offsets 0, 1, and 4096, you can predict what the output will be at offset 4097.

What it's missing: it's not that it's missing some little tweak (just change line 7 to use addition instead of xor, something like that). What it's missing is that it fundamentally wasn't designed to be cryptographically-strong. A cryptographically-strong PRNG needs to be designed in a very different way from a non-crypto PRNG. This was designed to be a non-crypto PRNG, and that's what it is. In particular, it sounds like MWC was designed to have a long period. But having a long period does not guarantee that a PRNG will be crypto-strength; not anywhere near it. Crypto-strength PRNGs have much stronger requirements, so there is no reason to expect that a statistical non-crypto PRNG will be cryptographically strong (it almost certainly won't be, if it wasn't designed to be). If you want a crypto-strength PRNG, you need to pick one that was designed to be that way from the start; you're not likely to fare well by picking a non-crypto PRNG and then trying to tweak it.

Anyway, I'm not sure why this question comes up. We have crypto-strength PRNGs that are secure, fast, and well-vetted. I don't know why one would mess around with trying to design your own based upon a non-crypto PRNG; that way leads to insecurity. If you think you can do better than the entire field at designing fast crypto-strength PRNGs... well, maybe you can, but I doubt the odds are on your side. Instead, I recommend you use a standard crypto-strength PRNG, if you need crypto-quality pseudorandom numbers.

share|improve this answer
6  
Wikipedia has a reasonable explanation of what "security" means. Note that no RNG that "work[s] by keeping a certain number, say k, of the most recently generated integers, then return[ing] the next integer as a function of those k" can possibly satisfy the next-bit test, because anyone who's seen its k most recently generated integers can predict its entire future output. –  Gordon Davisson Sep 15 '13 at 18:25
    
@GordonDavisson Funny enough, your “work[s] by keeping a certain number, say k, of the most recently generated integers, then return[ing] the next integer as a function of those k” would also fit those stream cipher designs, where the inner state is the base to create a next state via an NLFSR construction/function. (see Trivium, Mickey, etc.) I guess the choice of wording would be more optimal if your note would state “…as a linear function…”. –  e-sushi Jun 29 at 5:41
2  
@e-sushi: That's not the same thing, because a secure NLFSR generates its state update via one function, and its output via a different function. This allows the generator to hide its internal state (which is necessary for a secure PRNG). Something like MWC, on the other hand, uses the same function for state update and output, meaning that the output exposes the internal state directly. Nonlinearity can be useful, but is not directly on point here. –  Gordon Davisson Jun 29 at 17:33
    
@GordonDavisson Got it… btw: thanks for the reply to my rather late comment – much appreciated. –  e-sushi Jun 29 at 20:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.