# What stops the Multiply-With-Carry Random Number Generator from being a Cryptographically Secure Pseudo-Random Number Generator?

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?"

• 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

-
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
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
@D.W. What would be the implication of fronting the MWC with something like a Von Neuman de-biasing algorithm? You then wouldn't have access to outputs at offsets 0, 1, and 4096. Also, by having the conditional statement within the VN algorithm, doesn't that introduce non linearity to the output? MWC might not reach cryptographic standards, but wouldn't it be a lot more harder to reverse? –  Paul Uszak Aug 30 at 2:21

@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 '14 at 5:41
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.3627426028251648, "perplexity": 3255.2141771048305}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-35/segments/1440645390745.87/warc/CC-MAIN-20150827031630-00288-ip-10-171-96-226.ec2.internal.warc.gz"}